<!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Transitional//EN" "http://www.w3.org/TR/xhtml1/DTD/xhtml1-transitional.dtd">
<html xmlns="http://www.w3.org/1999/xhtml">
<head>
<meta http-equiv="Content-Type" content="text/xhtml;charset=UTF-8"/>
<meta http-equiv="X-UA-Compatible" content="IE=9"/>
<meta name="generator" content="Doxygen 1.8.10"/>
<title>Introduction_to_Algorithms: IntroductionToAlgorithm::GraphAlgorithm Namespace Reference</title>
<link href="tabs.css" rel="stylesheet" type="text/css"/>
<script type="text/javascript" src="jquery.js"></script>
<script type="text/javascript" src="dynsections.js"></script>
<link href="navtree.css" rel="stylesheet" type="text/css"/>
<script type="text/javascript" src="resize.js"></script>
<script type="text/javascript" src="navtreedata.js"></script>
<script type="text/javascript" src="navtree.js"></script>
<script type="text/javascript">
  $(document).ready(initResizable);
  $(window).load(resizeHeight);
</script>
<link href="search/search.css" rel="stylesheet" type="text/css"/>
<script type="text/javascript" src="search/searchdata.js"></script>
<script type="text/javascript" src="search/search.js"></script>
<script type="text/javascript">
  $(document).ready(function() { init_search(); });
</script>
<link href="doxygen.css" rel="stylesheet" type="text/css" />
</head>
<body>
<div id="top"><!-- do not remove this div, it is closed by doxygen! -->
<div id="titlearea">
<table cellspacing="0" cellpadding="0">
 <tbody>
 <tr style="height: 56px;">
  <td id="projectalign" style="padding-left: 0.5em;">
   <div id="projectname">Introduction_to_Algorithms
   </div>
  </td>
 </tr>
 </tbody>
</table>
</div>
<!-- end header part -->
<!-- Generated by Doxygen 1.8.10 -->
<script type="text/javascript">
var searchBox = new SearchBox("searchBox", "search",false,'Search');
</script>
  <div id="navrow1" class="tabs">
    <ul class="tablist">
      <li><a href="index.html"><span>Main&#160;Page</span></a></li>
      <li class="current"><a href="namespaces.html"><span>Namespaces</span></a></li>
      <li><a href="annotated.html"><span>Classes</span></a></li>
      <li><a href="files.html"><span>Files</span></a></li>
      <li>
        <div id="MSearchBox" class="MSearchBoxInactive">
        <span class="left">
          <img id="MSearchSelect" src="search/mag_sel.png"
               onmouseover="return searchBox.OnSearchSelectShow()"
               onmouseout="return searchBox.OnSearchSelectHide()"
               alt=""/>
          <input type="text" id="MSearchField" value="Search" accesskey="S"
               onfocus="searchBox.OnSearchFieldFocus(true)" 
               onblur="searchBox.OnSearchFieldFocus(false)" 
               onkeyup="searchBox.OnSearchFieldChange(event)"/>
          </span><span class="right">
            <a id="MSearchClose" href="javascript:searchBox.CloseResultsWindow()"><img id="MSearchCloseImg" border="0" src="search/close.png" alt=""/></a>
          </span>
        </div>
      </li>
    </ul>
  </div>
  <div id="navrow2" class="tabs2">
    <ul class="tablist">
      <li><a href="namespaces.html"><span>Namespace&#160;List</span></a></li>
      <li><a href="namespacemembers.html"><span>Namespace&#160;Members</span></a></li>
    </ul>
  </div>
</div><!-- top -->
<div id="side-nav" class="ui-resizable side-nav-resizable">
  <div id="nav-tree">
    <div id="nav-tree-contents">
      <div id="nav-sync" class="sync"></div>
    </div>
  </div>
  <div id="splitbar" style="-moz-user-select:none;" 
       class="ui-resizable-handle">
  </div>
</div>
<script type="text/javascript">
$(document).ready(function(){initNavTree('namespace_introduction_to_algorithm_1_1_graph_algorithm.html','');});
</script>
<div id="doc-content">
<!-- window showing the filter options -->
<div id="MSearchSelectWindow"
     onmouseover="return searchBox.OnSearchSelectShow()"
     onmouseout="return searchBox.OnSearchSelectHide()"
     onkeydown="return searchBox.OnSearchSelectKey(event)">
</div>

<!-- iframe showing the search results (closed by default) -->
<div id="MSearchResultsWindow">
<iframe src="javascript:void(0)" frameborder="0" 
        name="MSearchResults" id="MSearchResults">
</iframe>
</div>

<div class="header">
  <div class="summary">
<a href="#nested-classes">Classes</a> &#124;
<a href="#func-members">Functions</a>  </div>
  <div class="headertitle">
<div class="title">IntroductionToAlgorithm::GraphAlgorithm Namespace Reference</div>  </div>
</div><!--header-->
<div class="contents">

<p>Namespace of <a class="el" href="namespace_introduction_to_algorithm_1_1_graph_algorithm.html" title="Namespace of GraphAlgorithm. ">GraphAlgorithm</a>.  
<a href="#details">More...</a></p>
<table class="memberdecls">
<tr class="heading"><td colspan="2"><h2 class="groupheader"><a name="nested-classes"></a>
Classes</h2></td></tr>
<tr class="memitem:"><td class="memItemLeft" align="right" valign="top">struct &#160;</td><td class="memItemRight" valign="bottom"><a class="el" href="struct_introduction_to_algorithm_1_1_graph_algorithm_1_1_a_d_j_list_graph.html">ADJListGraph</a></td></tr>
<tr class="memdesc:"><td class="mdescLeft">&#160;</td><td class="mdescRight">ADJListGraph：图的邻接表表示，算法导论22章22.1节  <a href="struct_introduction_to_algorithm_1_1_graph_algorithm_1_1_a_d_j_list_graph.html#details">More...</a><br /></td></tr>
<tr class="separator:"><td class="memSeparator" colspan="2">&#160;</td></tr>
<tr class="memitem:"><td class="memItemLeft" align="right" valign="top">struct &#160;</td><td class="memItemRight" valign="bottom"><a class="el" href="struct_introduction_to_algorithm_1_1_graph_algorithm_1_1_b_f_s___vertex.html">BFS_Vertex</a></td></tr>
<tr class="memdesc:"><td class="mdescLeft">&#160;</td><td class="mdescRight">BFS_Vertex：用于广度优先搜索的顶点类型，算法导论22章22.2节  <a href="struct_introduction_to_algorithm_1_1_graph_algorithm_1_1_b_f_s___vertex.html#details">More...</a><br /></td></tr>
<tr class="separator:"><td class="memSeparator" colspan="2">&#160;</td></tr>
<tr class="memitem:"><td class="memItemLeft" align="right" valign="top">struct &#160;</td><td class="memItemRight" valign="bottom"><a class="el" href="struct_introduction_to_algorithm_1_1_graph_algorithm_1_1_d_f_s___vertex.html">DFS_Vertex</a></td></tr>
<tr class="memdesc:"><td class="mdescLeft">&#160;</td><td class="mdescRight">DFS_Vertex：用于深度优先搜索的顶点类型，算法导论22章22.3节  <a href="struct_introduction_to_algorithm_1_1_graph_algorithm_1_1_d_f_s___vertex.html#details">More...</a><br /></td></tr>
<tr class="separator:"><td class="memSeparator" colspan="2">&#160;</td></tr>
<tr class="memitem:"><td class="memItemLeft" align="right" valign="top">struct &#160;</td><td class="memItemRight" valign="bottom"><a class="el" href="struct_introduction_to_algorithm_1_1_graph_algorithm_1_1_edge.html">Edge</a></td></tr>
<tr class="memdesc:"><td class="mdescLeft">&#160;</td><td class="mdescRight">Edge：图的边，算法导论22章22.1节  <a href="struct_introduction_to_algorithm_1_1_graph_algorithm_1_1_edge.html#details">More...</a><br /></td></tr>
<tr class="separator:"><td class="memSeparator" colspan="2">&#160;</td></tr>
<tr class="memitem:"><td class="memItemLeft" align="right" valign="top">struct &#160;</td><td class="memItemRight" valign="bottom"><a class="el" href="struct_introduction_to_algorithm_1_1_graph_algorithm_1_1_flow_vertex.html">FlowVertex</a></td></tr>
<tr class="memdesc:"><td class="mdescLeft">&#160;</td><td class="mdescRight">FlowVertex：推送-重贴标签算法图的顶点，算法导论26章26.4节  <a href="struct_introduction_to_algorithm_1_1_graph_algorithm_1_1_flow_vertex.html#details">More...</a><br /></td></tr>
<tr class="separator:"><td class="memSeparator" colspan="2">&#160;</td></tr>
<tr class="memitem:"><td class="memItemLeft" align="right" valign="top">struct &#160;</td><td class="memItemRight" valign="bottom"><a class="el" href="struct_introduction_to_algorithm_1_1_graph_algorithm_1_1_front_flow_vertex.html">FrontFlowVertex</a></td></tr>
<tr class="memdesc:"><td class="mdescLeft">&#160;</td><td class="mdescRight">FrontFlowVertex：relabel_to_front算法的图的结点的数据结构，算法导论26章26.4节  <a href="struct_introduction_to_algorithm_1_1_graph_algorithm_1_1_front_flow_vertex.html#details">More...</a><br /></td></tr>
<tr class="separator:"><td class="memSeparator" colspan="2">&#160;</td></tr>
<tr class="memitem:"><td class="memItemLeft" align="right" valign="top">struct &#160;</td><td class="memItemRight" valign="bottom"><a class="el" href="struct_introduction_to_algorithm_1_1_graph_algorithm_1_1_graph.html">Graph</a></td></tr>
<tr class="memdesc:"><td class="mdescLeft">&#160;</td><td class="mdescRight">Graph：图，算法导论22章22.1节  <a href="struct_introduction_to_algorithm_1_1_graph_algorithm_1_1_graph.html#details">More...</a><br /></td></tr>
<tr class="separator:"><td class="memSeparator" colspan="2">&#160;</td></tr>
<tr class="memitem:"><td class="memItemLeft" align="right" valign="top">struct &#160;</td><td class="memItemRight" valign="bottom"><a class="el" href="struct_introduction_to_algorithm_1_1_graph_algorithm_1_1_list.html">List</a></td></tr>
<tr class="memdesc:"><td class="mdescLeft">&#160;</td><td class="mdescRight">List：链表数据结构  <a href="struct_introduction_to_algorithm_1_1_graph_algorithm_1_1_list.html#details">More...</a><br /></td></tr>
<tr class="separator:"><td class="memSeparator" colspan="2">&#160;</td></tr>
<tr class="memitem:"><td class="memItemLeft" align="right" valign="top">struct &#160;</td><td class="memItemRight" valign="bottom"><a class="el" href="struct_introduction_to_algorithm_1_1_graph_algorithm_1_1_list_node.html">ListNode</a></td></tr>
<tr class="memdesc:"><td class="mdescLeft">&#160;</td><td class="mdescRight">ListNode：链表结点的数据结构  <a href="struct_introduction_to_algorithm_1_1_graph_algorithm_1_1_list_node.html#details">More...</a><br /></td></tr>
<tr class="separator:"><td class="memSeparator" colspan="2">&#160;</td></tr>
<tr class="memitem:"><td class="memItemLeft" align="right" valign="top">struct &#160;</td><td class="memItemRight" valign="bottom"><a class="el" href="struct_introduction_to_algorithm_1_1_graph_algorithm_1_1_matrix_graph.html">MatrixGraph</a></td></tr>
<tr class="memdesc:"><td class="mdescLeft">&#160;</td><td class="mdescRight">MatrixGraph：图的矩阵表示，算法导论22章22.1节  <a href="struct_introduction_to_algorithm_1_1_graph_algorithm_1_1_matrix_graph.html#details">More...</a><br /></td></tr>
<tr class="separator:"><td class="memSeparator" colspan="2">&#160;</td></tr>
<tr class="memitem:"><td class="memItemLeft" align="right" valign="top">struct &#160;</td><td class="memItemRight" valign="bottom"><a class="el" href="struct_introduction_to_algorithm_1_1_graph_algorithm_1_1_set_vertex.html">SetVertex</a></td></tr>
<tr class="memdesc:"><td class="mdescLeft">&#160;</td><td class="mdescRight">SetVertex：图的顶点，它带一个node属性，算法导论22章22.1节  <a href="struct_introduction_to_algorithm_1_1_graph_algorithm_1_1_set_vertex.html#details">More...</a><br /></td></tr>
<tr class="separator:"><td class="memSeparator" colspan="2">&#160;</td></tr>
<tr class="memitem:"><td class="memItemLeft" align="right" valign="top">struct &#160;</td><td class="memItemRight" valign="bottom"><a class="el" href="struct_introduction_to_algorithm_1_1_graph_algorithm_1_1_vertex.html">Vertex</a></td></tr>
<tr class="memdesc:"><td class="mdescLeft">&#160;</td><td class="mdescRight">Vertex：图的顶点，算法导论22章22.1节  <a href="struct_introduction_to_algorithm_1_1_graph_algorithm_1_1_vertex.html#details">More...</a><br /></td></tr>
<tr class="separator:"><td class="memSeparator" colspan="2">&#160;</td></tr>
<tr class="memitem:"><td class="memItemLeft" align="right" valign="top">struct &#160;</td><td class="memItemRight" valign="bottom"><a class="el" href="struct_introduction_to_algorithm_1_1_graph_algorithm_1_1_vertex_p.html">VertexP</a></td></tr>
<tr class="memdesc:"><td class="mdescLeft">&#160;</td><td class="mdescRight">VertexP：图的顶点，它带一个parent属性，算法导论22章22.1节  <a href="struct_introduction_to_algorithm_1_1_graph_algorithm_1_1_vertex_p.html#details">More...</a><br /></td></tr>
<tr class="separator:"><td class="memSeparator" colspan="2">&#160;</td></tr>
</table><table class="memberdecls">
<tr class="heading"><td colspan="2"><h2 class="groupheader"><a name="func-members"></a>
Functions</h2></td></tr>
<tr class="memitem:ab951caca0797ff2907a180fe81609c70"><td class="memTemplParams" colspan="2">template&lt;typename GraphType &gt; </td></tr>
<tr class="memitem:ab951caca0797ff2907a180fe81609c70"><td class="memTemplItemLeft" align="right" valign="top">std::pair&lt; std::array&lt; std::array&lt; typename GraphType::EWeightType,GraphType::NUM &gt;, GraphType::NUM &gt;, std::array&lt; std::array&lt; typename GraphType::EWeightType,GraphType::NUM &gt;, GraphType::NUM &gt; &gt;&#160;</td><td class="memTemplItemRight" valign="bottom"><a class="el" href="namespace_introduction_to_algorithm_1_1_graph_algorithm.html#ab951caca0797ff2907a180fe81609c70">floyd_warshall</a> (std::shared_ptr&lt; GraphType &gt; graph)</td></tr>
<tr class="memdesc:ab951caca0797ff2907a180fe81609c70"><td class="mdescLeft">&#160;</td><td class="mdescRight">floyd_warshall：返回所有节点对的最短路径的floyd_warshall算法。算法导论25章25.2节  <a href="#ab951caca0797ff2907a180fe81609c70">More...</a><br /></td></tr>
<tr class="separator:ab951caca0797ff2907a180fe81609c70"><td class="memSeparator" colspan="2">&#160;</td></tr>
<tr class="memitem:a267d39a5bb09200f37a1cd2f0ad4f69f"><td class="memTemplParams" colspan="2">template&lt;typename GraphType &gt; </td></tr>
<tr class="memitem:a267d39a5bb09200f37a1cd2f0ad4f69f"><td class="memTemplItemLeft" align="right" valign="top">std::shared_ptr&lt; <a class="el" href="struct_introduction_to_algorithm_1_1_graph_algorithm_1_1_graph.html">Graph</a>&lt; GraphType::NUM+1, typename GraphType::VertexType &gt; &gt;&#160;</td><td class="memTemplItemRight" valign="bottom"><a class="el" href="namespace_introduction_to_algorithm_1_1_graph_algorithm.html#a267d39a5bb09200f37a1cd2f0ad4f69f">graph_plus_1v</a> (std::shared_ptr&lt; GraphType &gt; graph)</td></tr>
<tr class="memdesc:a267d39a5bb09200f37a1cd2f0ad4f69f"><td class="mdescLeft">&#160;</td><td class="mdescRight">graph_plus_1v：根据图graph生成一个新图。算法导论25章25.2节  <a href="#a267d39a5bb09200f37a1cd2f0ad4f69f">More...</a><br /></td></tr>
<tr class="separator:a267d39a5bb09200f37a1cd2f0ad4f69f"><td class="memSeparator" colspan="2">&#160;</td></tr>
<tr class="memitem:a856b132d068d0553355203a16cdec97d"><td class="memTemplParams" colspan="2">template&lt;typename GraphType &gt; </td></tr>
<tr class="memitem:a856b132d068d0553355203a16cdec97d"><td class="memTemplItemLeft" align="right" valign="top">std::array&lt; std::array&lt; typename GraphType::EWeightType,GraphType::NUM &gt;, GraphType::NUM &gt;&#160;</td><td class="memTemplItemRight" valign="bottom"><a class="el" href="namespace_introduction_to_algorithm_1_1_graph_algorithm.html#a856b132d068d0553355203a16cdec97d">johnson</a> (std::shared_ptr&lt; GraphType &gt; graph)</td></tr>
<tr class="memdesc:a856b132d068d0553355203a16cdec97d"><td class="mdescLeft">&#160;</td><td class="mdescRight">johnson：返回所有节点对的最短路径的johnson算法。算法导论25章25.3节  <a href="#a856b132d068d0553355203a16cdec97d">More...</a><br /></td></tr>
<tr class="separator:a856b132d068d0553355203a16cdec97d"><td class="memSeparator" colspan="2">&#160;</td></tr>
<tr class="memitem:a680307505286ae3230d1843c342e874e"><td class="memTemplParams" colspan="2">template&lt;typename MatrixType &gt; </td></tr>
<tr class="memitem:a680307505286ae3230d1843c342e874e"><td class="memTemplItemLeft" align="right" valign="top">MatrixType&#160;</td><td class="memTemplItemRight" valign="bottom"><a class="el" href="namespace_introduction_to_algorithm_1_1_graph_algorithm.html#a680307505286ae3230d1843c342e874e">extend_path</a> (const MatrixType &amp;L, const MatrixType &amp;W)</td></tr>
<tr class="memdesc:a680307505286ae3230d1843c342e874e"><td class="mdescLeft">&#160;</td><td class="mdescRight">extend_path：扩展一条边，算法导论25章25.1节  <a href="#a680307505286ae3230d1843c342e874e">More...</a><br /></td></tr>
<tr class="separator:a680307505286ae3230d1843c342e874e"><td class="memSeparator" colspan="2">&#160;</td></tr>
<tr class="memitem:ab9dcca59a42c708c137571d194c45bd9"><td class="memTemplParams" colspan="2">template&lt;typename GraphType &gt; </td></tr>
<tr class="memitem:ab9dcca59a42c708c137571d194c45bd9"><td class="memTemplItemLeft" align="right" valign="top">std::array&lt; std::array&lt; typename GraphType::EWeightType,GraphType::NUM &gt;, GraphType::NUM &gt;&#160;</td><td class="memTemplItemRight" valign="bottom"><a class="el" href="namespace_introduction_to_algorithm_1_1_graph_algorithm.html#ab9dcca59a42c708c137571d194c45bd9">matrix_shortest_path</a> (std::shared_ptr&lt; GraphType &gt; graph)</td></tr>
<tr class="memdesc:ab9dcca59a42c708c137571d194c45bd9"><td class="mdescLeft">&#160;</td><td class="mdescRight">matrix_shortest_path：返回所有节点对的最短路径的矩阵乘法算法。算法导论25章25.1节  <a href="#ab9dcca59a42c708c137571d194c45bd9">More...</a><br /></td></tr>
<tr class="separator:ab9dcca59a42c708c137571d194c45bd9"><td class="memSeparator" colspan="2">&#160;</td></tr>
<tr class="memitem:a6eb979447eeb937df4158f9646e20dde"><td class="memTemplParams" colspan="2">template&lt;typename GraphType &gt; </td></tr>
<tr class="memitem:a6eb979447eeb937df4158f9646e20dde"><td class="memTemplItemLeft" align="right" valign="top">std::array&lt; std::array&lt; typename GraphType::EWeightType,GraphType::NUM &gt;, GraphType::NUM &gt;&#160;</td><td class="memTemplItemRight" valign="bottom"><a class="el" href="namespace_introduction_to_algorithm_1_1_graph_algorithm.html#a6eb979447eeb937df4158f9646e20dde">matrix_shortest_path_fast</a> (std::shared_ptr&lt; GraphType &gt; graph)</td></tr>
<tr class="memdesc:a6eb979447eeb937df4158f9646e20dde"><td class="mdescLeft">&#160;</td><td class="mdescRight">matrix_shortest_path：返回所有节点对的最短路径的矩阵乘法复平方算法。算法导论25章25.1节  <a href="#a6eb979447eeb937df4158f9646e20dde">More...</a><br /></td></tr>
<tr class="separator:a6eb979447eeb937df4158f9646e20dde"><td class="memSeparator" colspan="2">&#160;</td></tr>
<tr class="memitem:a31fe8fc6f732112632c51221e739a7d4"><td class="memTemplParams" colspan="2">template&lt;typename GraphType &gt; </td></tr>
<tr class="memitem:a31fe8fc6f732112632c51221e739a7d4"><td class="memTemplItemLeft" align="right" valign="top">void&#160;</td><td class="memTemplItemRight" valign="bottom"><a class="el" href="namespace_introduction_to_algorithm_1_1_graph_algorithm.html#a31fe8fc6f732112632c51221e739a7d4">connected_component</a> (std::shared_ptr&lt; GraphType &gt; graph)</td></tr>
<tr class="memdesc:a31fe8fc6f732112632c51221e739a7d4"><td class="mdescLeft">&#160;</td><td class="mdescRight">connected_component：无向图的连通分量，算法导论21章21.1节  <a href="#a31fe8fc6f732112632c51221e739a7d4">More...</a><br /></td></tr>
<tr class="separator:a31fe8fc6f732112632c51221e739a7d4"><td class="memSeparator" colspan="2">&#160;</td></tr>
<tr class="memitem:ac368f242de9f06c7d936cba4aa0ab40b"><td class="memTemplParams" colspan="2">template&lt;typename GraphType &gt; </td></tr>
<tr class="memitem:ac368f242de9f06c7d936cba4aa0ab40b"><td class="memTemplItemLeft" align="right" valign="top">bool&#160;</td><td class="memTemplItemRight" valign="bottom"><a class="el" href="namespace_introduction_to_algorithm_1_1_graph_algorithm.html#ac368f242de9f06c7d936cba4aa0ab40b">same_component</a> (std::shared_ptr&lt; GraphType &gt; graph, typename GraphType::VIDType id1, typename GraphType::VIDType id2)</td></tr>
<tr class="memdesc:ac368f242de9f06c7d936cba4aa0ab40b"><td class="mdescLeft">&#160;</td><td class="mdescRight">same_component：返回无向图的两个顶点是否位于同一个连通分量中。算法导论21章21.1节  <a href="#ac368f242de9f06c7d936cba4aa0ab40b">More...</a><br /></td></tr>
<tr class="separator:ac368f242de9f06c7d936cba4aa0ab40b"><td class="memSeparator" colspan="2">&#160;</td></tr>
<tr class="memitem:a8839165b9e3d4c8c2ccac4cdc28aadd5"><td class="memTemplParams" colspan="2">template&lt;typename GraphType &gt; </td></tr>
<tr class="memitem:a8839165b9e3d4c8c2ccac4cdc28aadd5"><td class="memTemplItemLeft" align="right" valign="top">void&#160;</td><td class="memTemplItemRight" valign="bottom"><a class="el" href="namespace_introduction_to_algorithm_1_1_graph_algorithm.html#a8839165b9e3d4c8c2ccac4cdc28aadd5">breadth_first_search</a> (std::shared_ptr&lt; GraphType &gt; graph, typename GraphType::VIDType source_id, std::function&lt; void(typename GraphType::VIDType)&gt; pre_action=[](typename GraphType::VIDType){}, std::function&lt; void(typename GraphType::VIDType)&gt; post_action=[](typename GraphType::VIDType){})</td></tr>
<tr class="memdesc:a8839165b9e3d4c8c2ccac4cdc28aadd5"><td class="mdescLeft">&#160;</td><td class="mdescRight">breadth_first_search：广度优先搜索，算法导论22章22.2节  <a href="#a8839165b9e3d4c8c2ccac4cdc28aadd5">More...</a><br /></td></tr>
<tr class="separator:a8839165b9e3d4c8c2ccac4cdc28aadd5"><td class="memSeparator" colspan="2">&#160;</td></tr>
<tr class="memitem:a5fbba98b1c6a8b55f026158acc815768"><td class="memTemplParams" colspan="2">template&lt;typename GraphType &gt; </td></tr>
<tr class="memitem:a5fbba98b1c6a8b55f026158acc815768"><td class="memTemplItemLeft" align="right" valign="top">void&#160;</td><td class="memTemplItemRight" valign="bottom"><a class="el" href="namespace_introduction_to_algorithm_1_1_graph_algorithm.html#a5fbba98b1c6a8b55f026158acc815768">visit</a> (std::shared_ptr&lt; GraphType &gt; graph, typename GraphType::VIDType v_id, int &amp;time, std::function&lt; void(typename GraphType::VIDType, int)&gt; pre_action=[](typename GraphType::VIDType, int){}, std::function&lt; void(typename GraphType::VIDType, int)&gt; post_action=[](typename GraphType::VIDType, int){})</td></tr>
<tr class="memdesc:a5fbba98b1c6a8b55f026158acc815768"><td class="mdescLeft">&#160;</td><td class="mdescRight">visit：深度优先搜索的辅助函数，用于访问顶点，算法导论22章22.3节  <a href="#a5fbba98b1c6a8b55f026158acc815768">More...</a><br /></td></tr>
<tr class="separator:a5fbba98b1c6a8b55f026158acc815768"><td class="memSeparator" colspan="2">&#160;</td></tr>
<tr class="memitem:a9f44099f26242f50087b3cc16dff965f"><td class="memTemplParams" colspan="2">template&lt;typename GraphType &gt; </td></tr>
<tr class="memitem:a9f44099f26242f50087b3cc16dff965f"><td class="memTemplItemLeft" align="right" valign="top">void&#160;</td><td class="memTemplItemRight" valign="bottom"><a class="el" href="namespace_introduction_to_algorithm_1_1_graph_algorithm.html#a9f44099f26242f50087b3cc16dff965f">depth_first_search</a> (std::shared_ptr&lt; GraphType &gt; graph, std::function&lt; void(typename GraphType::VIDType, int)&gt; pre_action=[](typename GraphType::VIDType, int){}, std::function&lt; void(typename GraphType::VIDType, int)&gt; post_action=[](typename GraphType::VIDType, int){}, std::function&lt; void(typename GraphType::VIDType, int)&gt; pre_root_action=[](typename GraphType::VIDType, int){}, std::function&lt; void(typename GraphType::VIDType, int)&gt; post_root_action=[](typename GraphType::VIDType, int){}, const std::vector&lt; typename GraphType::VIDType &gt; &amp;search_order=std::vector&lt; typename GraphType::VIDType &gt;())</td></tr>
<tr class="memdesc:a9f44099f26242f50087b3cc16dff965f"><td class="mdescLeft">&#160;</td><td class="mdescRight">depth_first_search：深度优先搜索，算法导论22章22.3节  <a href="#a9f44099f26242f50087b3cc16dff965f">More...</a><br /></td></tr>
<tr class="separator:a9f44099f26242f50087b3cc16dff965f"><td class="memSeparator" colspan="2">&#160;</td></tr>
<tr class="memitem:a6d058c2aaa8714778b3f2ab8a24ff232"><td class="memTemplParams" colspan="2">template&lt;typename GraphType &gt; </td></tr>
<tr class="memitem:a6d058c2aaa8714778b3f2ab8a24ff232"><td class="memTemplItemLeft" align="right" valign="top">const std::vector&lt; std::vector&lt; typename GraphType::VIDType &gt; &gt;&#160;</td><td class="memTemplItemRight" valign="bottom"><a class="el" href="namespace_introduction_to_algorithm_1_1_graph_algorithm.html#a6d058c2aaa8714778b3f2ab8a24ff232">scc</a> (std::shared_ptr&lt; GraphType &gt; graph)</td></tr>
<tr class="memdesc:a6d058c2aaa8714778b3f2ab8a24ff232"><td class="mdescLeft">&#160;</td><td class="mdescRight">scc：强连通分量，算法导论22章22.5节  <a href="#a6d058c2aaa8714778b3f2ab8a24ff232">More...</a><br /></td></tr>
<tr class="separator:a6d058c2aaa8714778b3f2ab8a24ff232"><td class="memSeparator" colspan="2">&#160;</td></tr>
<tr class="memitem:a804241e72be5f4c031190bc12a6b73a2"><td class="memTemplParams" colspan="2">template&lt;typename GraphType &gt; </td></tr>
<tr class="memitem:a804241e72be5f4c031190bc12a6b73a2"><td class="memTemplItemLeft" align="right" valign="top">std::vector&lt; typename GraphType::VIDType &gt;&#160;</td><td class="memTemplItemRight" valign="bottom"><a class="el" href="namespace_introduction_to_algorithm_1_1_graph_algorithm.html#a804241e72be5f4c031190bc12a6b73a2">topology_sort</a> (std::shared_ptr&lt; GraphType &gt; graph)</td></tr>
<tr class="memdesc:a804241e72be5f4c031190bc12a6b73a2"><td class="mdescLeft">&#160;</td><td class="mdescRight">topology_sort：拓扑排序，算法导论22章22.4节  <a href="#a804241e72be5f4c031190bc12a6b73a2">More...</a><br /></td></tr>
<tr class="separator:a804241e72be5f4c031190bc12a6b73a2"><td class="memSeparator" colspan="2">&#160;</td></tr>
<tr class="memitem:acc8cd65d7cf2d584f86cfd92494bdbf4"><td class="memTemplParams" colspan="2">template&lt;typename GraphType &gt; </td></tr>
<tr class="memitem:acc8cd65d7cf2d584f86cfd92494bdbf4"><td class="memTemplItemLeft" align="right" valign="top">std::shared_ptr&lt; GraphType &gt;&#160;</td><td class="memTemplItemRight" valign="bottom"><a class="el" href="namespace_introduction_to_algorithm_1_1_graph_algorithm.html#acc8cd65d7cf2d584f86cfd92494bdbf4">create_Gf</a> (const std::shared_ptr&lt; GraphType &gt; graph, std::array&lt; std::array&lt; typename GraphType::EWeightType, GraphType::NUM &gt;, GraphType::NUM &gt; &amp;flow)</td></tr>
<tr class="memdesc:acc8cd65d7cf2d584f86cfd92494bdbf4"><td class="mdescLeft">&#160;</td><td class="mdescRight">create_Gf：根据指定流网络生成一个残余网络。算法导论26章26.2节  <a href="#acc8cd65d7cf2d584f86cfd92494bdbf4">More...</a><br /></td></tr>
<tr class="separator:acc8cd65d7cf2d584f86cfd92494bdbf4"><td class="memSeparator" colspan="2">&#160;</td></tr>
<tr class="memitem:a23a29754883e1edd7bd95a76634444a2"><td class="memTemplParams" colspan="2">template&lt;typename GraphType &gt; </td></tr>
<tr class="memitem:a23a29754883e1edd7bd95a76634444a2"><td class="memTemplItemLeft" align="right" valign="top">std::array&lt; std::array&lt; typename GraphType::EWeightType, GraphType::NUM &gt;, GraphType::NUM &gt;&#160;</td><td class="memTemplItemRight" valign="bottom"><a class="el" href="namespace_introduction_to_algorithm_1_1_graph_algorithm.html#a23a29754883e1edd7bd95a76634444a2">ford_fulkerson</a> (const std::shared_ptr&lt; GraphType &gt; graph, typename GraphType::VIDType src, typename GraphType::VIDType dst)</td></tr>
<tr class="memdesc:a23a29754883e1edd7bd95a76634444a2"><td class="mdescLeft">&#160;</td><td class="mdescRight">ford_fulkerson：最大流的ford_fulkerson算法。算法导论26章26.2节  <a href="#a23a29754883e1edd7bd95a76634444a2">More...</a><br /></td></tr>
<tr class="separator:a23a29754883e1edd7bd95a76634444a2"><td class="memSeparator" colspan="2">&#160;</td></tr>
<tr class="memitem:abd520b7e33d8c1e72b05210d784ac258"><td class="memTemplParams" colspan="2">template&lt;typename GraphType &gt; </td></tr>
<tr class="memitem:abd520b7e33d8c1e72b05210d784ac258"><td class="memTemplItemLeft" align="right" valign="top">void&#160;</td><td class="memTemplItemRight" valign="bottom"><a class="el" href="namespace_introduction_to_algorithm_1_1_graph_algorithm.html#abd520b7e33d8c1e72b05210d784ac258">push</a> (std::shared_ptr&lt; GraphType &gt; graph, typename GraphType::VIDType u_id, typename GraphType::VIDType v_id, std::array&lt; std::array&lt; typename GraphType::EWeightType, GraphType::NUM &gt;, GraphType::NUM &gt; &amp;flow)</td></tr>
<tr class="memdesc:abd520b7e33d8c1e72b05210d784ac258"><td class="mdescLeft">&#160;</td><td class="mdescRight">push：generic_push_relabel算法的push操作。算法导论26章26.4节  <a href="#abd520b7e33d8c1e72b05210d784ac258">More...</a><br /></td></tr>
<tr class="separator:abd520b7e33d8c1e72b05210d784ac258"><td class="memSeparator" colspan="2">&#160;</td></tr>
<tr class="memitem:a27dfe859312abba6639bca7b232d4bd6"><td class="memTemplParams" colspan="2">template&lt;typename GraphType &gt; </td></tr>
<tr class="memitem:a27dfe859312abba6639bca7b232d4bd6"><td class="memTemplItemLeft" align="right" valign="top">GraphType::VIDType&#160;</td><td class="memTemplItemRight" valign="bottom"><a class="el" href="namespace_introduction_to_algorithm_1_1_graph_algorithm.html#a27dfe859312abba6639bca7b232d4bd6">min_v_at_Ef</a> (std::shared_ptr&lt; GraphType &gt; graph, typename GraphType::VIDType u_id, const std::array&lt; std::array&lt; typename GraphType::EWeightType, GraphType::NUM &gt;, GraphType::NUM &gt; &amp;flow)</td></tr>
<tr class="memdesc:a27dfe859312abba6639bca7b232d4bd6"><td class="mdescLeft">&#160;</td><td class="mdescRight">min_v_at_Ef：relabel操作中的min_v_at_Ef操作。算法导论26章26.4节  <a href="#a27dfe859312abba6639bca7b232d4bd6">More...</a><br /></td></tr>
<tr class="separator:a27dfe859312abba6639bca7b232d4bd6"><td class="memSeparator" colspan="2">&#160;</td></tr>
<tr class="memitem:a143924362cc9f23ca452c3ca0e292ff3"><td class="memTemplParams" colspan="2">template&lt;typename GraphType &gt; </td></tr>
<tr class="memitem:a143924362cc9f23ca452c3ca0e292ff3"><td class="memTemplItemLeft" align="right" valign="top">void&#160;</td><td class="memTemplItemRight" valign="bottom"><a class="el" href="namespace_introduction_to_algorithm_1_1_graph_algorithm.html#a143924362cc9f23ca452c3ca0e292ff3">relabel</a> (std::shared_ptr&lt; GraphType &gt; graph, typename GraphType::VIDType u_id, const std::array&lt; std::array&lt; typename GraphType::EWeightType, GraphType::NUM &gt;, GraphType::NUM &gt; &amp;flow)</td></tr>
<tr class="memdesc:a143924362cc9f23ca452c3ca0e292ff3"><td class="mdescLeft">&#160;</td><td class="mdescRight">relabel：generic_push_relabel算法的relabel操作。算法导论26章26.4节  <a href="#a143924362cc9f23ca452c3ca0e292ff3">More...</a><br /></td></tr>
<tr class="separator:a143924362cc9f23ca452c3ca0e292ff3"><td class="memSeparator" colspan="2">&#160;</td></tr>
<tr class="memitem:aeaf3e258f5ae9aed76158255fa603c00"><td class="memTemplParams" colspan="2">template&lt;typename GraphType &gt; </td></tr>
<tr class="memitem:aeaf3e258f5ae9aed76158255fa603c00"><td class="memTemplItemLeft" align="right" valign="top">void&#160;</td><td class="memTemplItemRight" valign="bottom"><a class="el" href="namespace_introduction_to_algorithm_1_1_graph_algorithm.html#aeaf3e258f5ae9aed76158255fa603c00">initialize_preflow</a> (std::shared_ptr&lt; GraphType &gt; graph, typename GraphType::VIDType src, std::array&lt; std::array&lt; typename GraphType::EWeightType, GraphType::NUM &gt;, GraphType::NUM &gt; &amp;flow)</td></tr>
<tr class="memdesc:aeaf3e258f5ae9aed76158255fa603c00"><td class="mdescLeft">&#160;</td><td class="mdescRight">initialize_preflow：generic_push_relabel算法的初始化操作。算法导论26章26.4节  <a href="#aeaf3e258f5ae9aed76158255fa603c00">More...</a><br /></td></tr>
<tr class="separator:aeaf3e258f5ae9aed76158255fa603c00"><td class="memSeparator" colspan="2">&#160;</td></tr>
<tr class="memitem:ab134ec014d01e25ec2ed7d2c97babe23"><td class="memTemplParams" colspan="2">template&lt;typename GraphType &gt; </td></tr>
<tr class="memitem:ab134ec014d01e25ec2ed7d2c97babe23"><td class="memTemplItemLeft" align="right" valign="top">std::array&lt; std::array&lt; typename GraphType::EWeightType, GraphType::NUM &gt;, GraphType::NUM &gt;&#160;</td><td class="memTemplItemRight" valign="bottom"><a class="el" href="namespace_introduction_to_algorithm_1_1_graph_algorithm.html#ab134ec014d01e25ec2ed7d2c97babe23">generic_push_relabel</a> (std::shared_ptr&lt; GraphType &gt; graph, typename GraphType::VIDType src, typename GraphType::VIDType dst)</td></tr>
<tr class="memdesc:ab134ec014d01e25ec2ed7d2c97babe23"><td class="mdescLeft">&#160;</td><td class="mdescRight">generic_push_relabel：最大流的推送-重贴标签算法。算法导论26章26.4节  <a href="#ab134ec014d01e25ec2ed7d2c97babe23">More...</a><br /></td></tr>
<tr class="separator:ab134ec014d01e25ec2ed7d2c97babe23"><td class="memSeparator" colspan="2">&#160;</td></tr>
<tr class="memitem:a2ae42c12c93664d94b5a6f9980fe8540"><td class="memTemplParams" colspan="2">template&lt;typename GraphType &gt; </td></tr>
<tr class="memitem:a2ae42c12c93664d94b5a6f9980fe8540"><td class="memTemplItemLeft" align="right" valign="top">void&#160;</td><td class="memTemplItemRight" valign="bottom"><a class="el" href="namespace_introduction_to_algorithm_1_1_graph_algorithm.html#a2ae42c12c93664d94b5a6f9980fe8540">discharge</a> (std::shared_ptr&lt; GraphType &gt; graph, typename GraphType::VIDType u_id, std::array&lt; std::array&lt; typename GraphType::EWeightType, GraphType::NUM &gt;, GraphType::NUM &gt; &amp;flow)</td></tr>
<tr class="memdesc:a2ae42c12c93664d94b5a6f9980fe8540"><td class="mdescLeft">&#160;</td><td class="mdescRight">discharge：最大流的前置重贴标签算法中的释放操作。算法导论26章26.5节  <a href="#a2ae42c12c93664d94b5a6f9980fe8540">More...</a><br /></td></tr>
<tr class="separator:a2ae42c12c93664d94b5a6f9980fe8540"><td class="memSeparator" colspan="2">&#160;</td></tr>
<tr class="memitem:ad6a1917551c87991625d8402593ec863"><td class="memTemplParams" colspan="2">template&lt;typename GraphType &gt; </td></tr>
<tr class="memitem:ad6a1917551c87991625d8402593ec863"><td class="memTemplItemLeft" align="right" valign="top"><a class="el" href="struct_introduction_to_algorithm_1_1_graph_algorithm_1_1_list.html">List</a>&lt; <a class="el" href="struct_introduction_to_algorithm_1_1_graph_algorithm_1_1_list_node.html">ListNode</a>&lt; typename GraphType::VertexType &gt; &gt;&#160;</td><td class="memTemplItemRight" valign="bottom"><a class="el" href="namespace_introduction_to_algorithm_1_1_graph_algorithm.html#ad6a1917551c87991625d8402593ec863">create_L</a> (std::shared_ptr&lt; GraphType &gt; graph, typename GraphType::VIDType src, typename GraphType::VIDType dst)</td></tr>
<tr class="memdesc:ad6a1917551c87991625d8402593ec863"><td class="mdescLeft">&#160;</td><td class="mdescRight">create_L：前置重贴标签算法中的创建L链表操作  <a href="#ad6a1917551c87991625d8402593ec863">More...</a><br /></td></tr>
<tr class="separator:ad6a1917551c87991625d8402593ec863"><td class="memSeparator" colspan="2">&#160;</td></tr>
<tr class="memitem:af1dfc9c1874850fb1415db3644497777"><td class="memTemplParams" colspan="2">template&lt;typename GraphType &gt; </td></tr>
<tr class="memitem:af1dfc9c1874850fb1415db3644497777"><td class="memTemplItemLeft" align="right" valign="top">void&#160;</td><td class="memTemplItemRight" valign="bottom"><a class="el" href="namespace_introduction_to_algorithm_1_1_graph_algorithm.html#af1dfc9c1874850fb1415db3644497777">initial_vertex_NList</a> (std::shared_ptr&lt; GraphType &gt; graph, typename GraphType::VIDType src, typename GraphType::VIDType dst)</td></tr>
<tr class="memdesc:af1dfc9c1874850fb1415db3644497777"><td class="mdescLeft">&#160;</td><td class="mdescRight">initial_vertex_NList：前置重贴标签算法中的初始化邻接链表操作  <a href="#af1dfc9c1874850fb1415db3644497777">More...</a><br /></td></tr>
<tr class="separator:af1dfc9c1874850fb1415db3644497777"><td class="memSeparator" colspan="2">&#160;</td></tr>
<tr class="memitem:abafb73bda29c4e389edb048a5e5d8d2b"><td class="memTemplParams" colspan="2">template&lt;typename GraphType &gt; </td></tr>
<tr class="memitem:abafb73bda29c4e389edb048a5e5d8d2b"><td class="memTemplItemLeft" align="right" valign="top">std::array&lt; std::array&lt; typename GraphType::EWeightType, GraphType::NUM &gt;, GraphType::NUM &gt;&#160;</td><td class="memTemplItemRight" valign="bottom"><a class="el" href="namespace_introduction_to_algorithm_1_1_graph_algorithm.html#abafb73bda29c4e389edb048a5e5d8d2b">relabel_to_front</a> (std::shared_ptr&lt; GraphType &gt; graph, typename GraphType::VIDType src, typename GraphType::VIDType dst)</td></tr>
<tr class="memdesc:abafb73bda29c4e389edb048a5e5d8d2b"><td class="mdescLeft">&#160;</td><td class="mdescRight">relabel_to_front：最大流的前置重贴标签算法。算法导论26章26.5节  <a href="#abafb73bda29c4e389edb048a5e5d8d2b">More...</a><br /></td></tr>
<tr class="separator:abafb73bda29c4e389edb048a5e5d8d2b"><td class="memSeparator" colspan="2">&#160;</td></tr>
<tr class="memitem:a2575c09c42d0b30b57702c9379d2fbfb"><td class="memTemplParams" colspan="2">template&lt;typename GraphType , typename ActionType  = std::function&lt; void(typename GraphType::VIDType,typename GraphType::VIDType)&gt;&gt; </td></tr>
<tr class="memitem:a2575c09c42d0b30b57702c9379d2fbfb"><td class="memTemplItemLeft" align="right" valign="top">GraphType::EWeightType&#160;</td><td class="memTemplItemRight" valign="bottom"><a class="el" href="namespace_introduction_to_algorithm_1_1_graph_algorithm.html#a2575c09c42d0b30b57702c9379d2fbfb">kruskal</a> (std::shared_ptr&lt; GraphType &gt; graph, ActionType pre_action=[](typename GraphType::VIDType, typename GraphType::VIDType){}, ActionType post_action=[](typename GraphType::VIDType, typename GraphType::VIDType){})</td></tr>
<tr class="memdesc:a2575c09c42d0b30b57702c9379d2fbfb"><td class="mdescLeft">&#160;</td><td class="mdescRight">kruskal：最小生成树的Kruskal算法，算法导论23章23.2节  <a href="#a2575c09c42d0b30b57702c9379d2fbfb">More...</a><br /></td></tr>
<tr class="separator:a2575c09c42d0b30b57702c9379d2fbfb"><td class="memSeparator" colspan="2">&#160;</td></tr>
<tr class="memitem:aba1581358d79ba82dc4fd0c15bc987e6"><td class="memTemplParams" colspan="2">template&lt;typename GraphType , typename ActionType  = std::function&lt; void(typename GraphType::VIDType)&gt;&gt; </td></tr>
<tr class="memitem:aba1581358d79ba82dc4fd0c15bc987e6"><td class="memTemplItemLeft" align="right" valign="top">GraphType::EWeightType&#160;</td><td class="memTemplItemRight" valign="bottom"><a class="el" href="namespace_introduction_to_algorithm_1_1_graph_algorithm.html#aba1581358d79ba82dc4fd0c15bc987e6">prim</a> (std::shared_ptr&lt; GraphType &gt; graph, typename GraphType::VIDType source_id, ActionType pre_action=[](typename GraphType::VIDType){}, ActionType post_action=[](typename GraphType::VIDType){})</td></tr>
<tr class="memdesc:aba1581358d79ba82dc4fd0c15bc987e6"><td class="mdescLeft">&#160;</td><td class="mdescRight">prim：最小生成树的Prim算法，算法导论23章23.2节  <a href="#aba1581358d79ba82dc4fd0c15bc987e6">More...</a><br /></td></tr>
<tr class="separator:aba1581358d79ba82dc4fd0c15bc987e6"><td class="memSeparator" colspan="2">&#160;</td></tr>
<tr class="memitem:a5ed496e8825564d0f9fcfe3b0ac41dec"><td class="memTemplParams" colspan="2">template&lt;typename GraphType &gt; </td></tr>
<tr class="memitem:a5ed496e8825564d0f9fcfe3b0ac41dec"><td class="memTemplItemLeft" align="right" valign="top">void&#160;</td><td class="memTemplItemRight" valign="bottom"><a class="el" href="namespace_introduction_to_algorithm_1_1_graph_algorithm.html#a5ed496e8825564d0f9fcfe3b0ac41dec">initialize_single_source</a> (std::shared_ptr&lt; GraphType &gt; graph, typename GraphType::VIDType source_id)</td></tr>
<tr class="memdesc:a5ed496e8825564d0f9fcfe3b0ac41dec"><td class="mdescLeft">&#160;</td><td class="mdescRight">initialize_single_source：单源最短路径的初始化操作，算法导论24章24.1节  <a href="#a5ed496e8825564d0f9fcfe3b0ac41dec">More...</a><br /></td></tr>
<tr class="separator:a5ed496e8825564d0f9fcfe3b0ac41dec"><td class="memSeparator" colspan="2">&#160;</td></tr>
<tr class="memitem:afe2bd83fca7df7e07ece9a59b8e7f5a6"><td class="memTemplParams" colspan="2">template&lt;typename VertexType &gt; </td></tr>
<tr class="memitem:afe2bd83fca7df7e07ece9a59b8e7f5a6"><td class="memTemplItemLeft" align="right" valign="top">void&#160;</td><td class="memTemplItemRight" valign="bottom"><a class="el" href="namespace_introduction_to_algorithm_1_1_graph_algorithm.html#afe2bd83fca7df7e07ece9a59b8e7f5a6">relax</a> (std::shared_ptr&lt; VertexType &gt; from, std::shared_ptr&lt; VertexType &gt; to, typename VertexType::KeyType weight)</td></tr>
<tr class="memdesc:afe2bd83fca7df7e07ece9a59b8e7f5a6"><td class="mdescLeft">&#160;</td><td class="mdescRight">relax：单源最短路径的松弛操作，算法导论24章24.1节  <a href="#afe2bd83fca7df7e07ece9a59b8e7f5a6">More...</a><br /></td></tr>
<tr class="separator:afe2bd83fca7df7e07ece9a59b8e7f5a6"><td class="memSeparator" colspan="2">&#160;</td></tr>
<tr class="memitem:ae96d9b844260ee3ce9225055040c631b"><td class="memTemplParams" colspan="2">template&lt;typename GraphType &gt; </td></tr>
<tr class="memitem:ae96d9b844260ee3ce9225055040c631b"><td class="memTemplItemLeft" align="right" valign="top">bool&#160;</td><td class="memTemplItemRight" valign="bottom"><a class="el" href="namespace_introduction_to_algorithm_1_1_graph_algorithm.html#ae96d9b844260ee3ce9225055040c631b">bellman_ford</a> (std::shared_ptr&lt; GraphType &gt; graph, typename GraphType::VIDType source_id)</td></tr>
<tr class="memdesc:ae96d9b844260ee3ce9225055040c631b"><td class="mdescLeft">&#160;</td><td class="mdescRight">bellman_ford：单源最短路径的bellman_ford算法，算法导论24章24.1节  <a href="#ae96d9b844260ee3ce9225055040c631b">More...</a><br /></td></tr>
<tr class="separator:ae96d9b844260ee3ce9225055040c631b"><td class="memSeparator" colspan="2">&#160;</td></tr>
<tr class="memitem:aec7fe196e6aee4c8e6004a05495c8813"><td class="memTemplParams" colspan="2">template&lt;typename GraphType &gt; </td></tr>
<tr class="memitem:aec7fe196e6aee4c8e6004a05495c8813"><td class="memTemplItemLeft" align="right" valign="top">void&#160;</td><td class="memTemplItemRight" valign="bottom"><a class="el" href="namespace_introduction_to_algorithm_1_1_graph_algorithm.html#aec7fe196e6aee4c8e6004a05495c8813">dag_shortest_path</a> (std::shared_ptr&lt; GraphType &gt; graph, typename GraphType::VIDType source_id)</td></tr>
<tr class="memdesc:aec7fe196e6aee4c8e6004a05495c8813"><td class="mdescLeft">&#160;</td><td class="mdescRight">dag_shortest_path：有向无环图的单源最短路径的dag_shortest_path算法，算法导论24章24.2节  <a href="#aec7fe196e6aee4c8e6004a05495c8813">More...</a><br /></td></tr>
<tr class="separator:aec7fe196e6aee4c8e6004a05495c8813"><td class="memSeparator" colspan="2">&#160;</td></tr>
<tr class="memitem:acac554e111d6377c630865258dd6aa19"><td class="memTemplParams" colspan="2">template&lt;typename GraphType &gt; </td></tr>
<tr class="memitem:acac554e111d6377c630865258dd6aa19"><td class="memTemplItemLeft" align="right" valign="top">void&#160;</td><td class="memTemplItemRight" valign="bottom"><a class="el" href="namespace_introduction_to_algorithm_1_1_graph_algorithm.html#acac554e111d6377c630865258dd6aa19">dijkstra</a> (std::shared_ptr&lt; GraphType &gt; graph, typename GraphType::VIDType source_id)</td></tr>
<tr class="memdesc:acac554e111d6377c630865258dd6aa19"><td class="mdescLeft">&#160;</td><td class="mdescRight">dijkstra：单源最短路径的dijkstra算法，算法导论24章24.3节  <a href="#acac554e111d6377c630865258dd6aa19">More...</a><br /></td></tr>
<tr class="separator:acac554e111d6377c630865258dd6aa19"><td class="memSeparator" colspan="2">&#160;</td></tr>
<tr class="memitem:a19237111c3b1ec2717c5e1aefe2f6d9b"><td class="memTemplParams" colspan="2">template&lt;typename T &gt; </td></tr>
<tr class="memitem:a19237111c3b1ec2717c5e1aefe2f6d9b"><td class="memTemplItemLeft" align="right" valign="top">T&#160;</td><td class="memTemplItemRight" valign="bottom"><a class="el" href="namespace_introduction_to_algorithm_1_1_graph_algorithm.html#a19237111c3b1ec2717c5e1aefe2f6d9b">unlimit</a> ()</td></tr>
<tr class="memdesc:a19237111c3b1ec2717c5e1aefe2f6d9b"><td class="mdescLeft">&#160;</td><td class="mdescRight">unlimit：返回正无穷的函数  <a href="#a19237111c3b1ec2717c5e1aefe2f6d9b">More...</a><br /></td></tr>
<tr class="separator:a19237111c3b1ec2717c5e1aefe2f6d9b"><td class="memSeparator" colspan="2">&#160;</td></tr>
<tr class="memitem:a4f664c13605fc87ca8d26f4aad5a9fa2"><td class="memTemplParams" colspan="2">template&lt;typename T &gt; </td></tr>
<tr class="memitem:a4f664c13605fc87ca8d26f4aad5a9fa2"><td class="memTemplItemLeft" align="right" valign="top">bool&#160;</td><td class="memTemplItemRight" valign="bottom"><a class="el" href="namespace_introduction_to_algorithm_1_1_graph_algorithm.html#a4f664c13605fc87ca8d26f4aad5a9fa2">is_unlimit</a> (T t)</td></tr>
<tr class="memdesc:a4f664c13605fc87ca8d26f4aad5a9fa2"><td class="mdescLeft">&#160;</td><td class="mdescRight">is_unlimit：判断是否正无穷  <a href="#a4f664c13605fc87ca8d26f4aad5a9fa2">More...</a><br /></td></tr>
<tr class="separator:a4f664c13605fc87ca8d26f4aad5a9fa2"><td class="memSeparator" colspan="2">&#160;</td></tr>
<tr class="memitem:a1581960f77507024b39572aeb6d1fbd6"><td class="memTemplParams" colspan="2">template&lt;typename VertexType &gt; </td></tr>
<tr class="memitem:a1581960f77507024b39572aeb6d1fbd6"><td class="memTemplItemLeft" align="right" valign="top">std::vector&lt; typename VertexType::VIDType &gt;&#160;</td><td class="memTemplItemRight" valign="bottom"><a class="el" href="namespace_introduction_to_algorithm_1_1_graph_algorithm.html#a1581960f77507024b39572aeb6d1fbd6">get_path</a> (const std::shared_ptr&lt; VertexType &gt; v_from, const std::shared_ptr&lt; VertexType &gt; v_to)</td></tr>
<tr class="memdesc:a1581960f77507024b39572aeb6d1fbd6"><td class="mdescLeft">&#160;</td><td class="mdescRight">get_path：获取两个顶点之间的路径  <a href="#a1581960f77507024b39572aeb6d1fbd6">More...</a><br /></td></tr>
<tr class="separator:a1581960f77507024b39572aeb6d1fbd6"><td class="memSeparator" colspan="2">&#160;</td></tr>
<tr class="memitem:a97d248a07f1b31df52be3de3b5570237"><td class="memTemplParams" colspan="2">template&lt;typename MatrixType &gt; </td></tr>
<tr class="memitem:a97d248a07f1b31df52be3de3b5570237"><td class="memTemplItemLeft" align="right" valign="top">std::string&#160;</td><td class="memTemplItemRight" valign="bottom"><a class="el" href="namespace_introduction_to_algorithm_1_1_graph_algorithm.html#a97d248a07f1b31df52be3de3b5570237">matrix_string</a> (const MatrixType &amp;matrix)</td></tr>
<tr class="memdesc:a97d248a07f1b31df52be3de3b5570237"><td class="mdescLeft">&#160;</td><td class="mdescRight">matrix_string：获取矩阵的字符串描述  <a href="#a97d248a07f1b31df52be3de3b5570237">More...</a><br /></td></tr>
<tr class="separator:a97d248a07f1b31df52be3de3b5570237"><td class="memSeparator" colspan="2">&#160;</td></tr>
</table>
<a name="details" id="details"></a><h2 class="groupheader">Detailed Description</h2>
<div class="textblock"><p>Namespace of <a class="el" href="namespace_introduction_to_algorithm_1_1_graph_algorithm.html" title="Namespace of GraphAlgorithm. ">GraphAlgorithm</a>. </p>
<p>该命名空间内包含所有图算法 </p>
</div><h2 class="groupheader">Function Documentation</h2>
<a class="anchor" id="ae96d9b844260ee3ce9225055040c631b"></a>
<div class="memitem">
<div class="memproto">
<div class="memtemplate">
template&lt;typename GraphType &gt; </div>
      <table class="memname">
        <tr>
          <td class="memname">bool IntroductionToAlgorithm::GraphAlgorithm::bellman_ford </td>
          <td>(</td>
          <td class="paramtype">std::shared_ptr&lt; GraphType &gt;&#160;</td>
          <td class="paramname"><em>graph</em>, </td>
        </tr>
        <tr>
          <td class="paramkey"></td>
          <td></td>
          <td class="paramtype">typename GraphType::VIDType&#160;</td>
          <td class="paramname"><em>source_id</em>&#160;</td>
        </tr>
        <tr>
          <td></td>
          <td>)</td>
          <td></td><td></td>
        </tr>
      </table>
</div><div class="memdoc">

<p>bellman_ford：单源最短路径的bellman_ford算法，算法导论24章24.1节 </p>
<dl class="params"><dt>Parameters</dt><dd>
  <table class="params">
    <tr><td class="paramname">graph:指向图的强指针，必须非空。若为空则抛出异常</td><td></td></tr>
    <tr><td class="paramname">source_id：最小生成树的根结点&lt;tt&gt;id&lt;/tt&gt;，必须有效。若无效则抛出异常</td><td></td></tr>
  </table>
  </dd>
</dl>
<dl class="section return"><dt>Returns</dt><dd>: 是否不包含可以从源结点可达的权重为负值的环路。若返回值为true，则说明不包含可以从源结点可达的权重为负值的环路</dd></dl>
<h2>单源最短路径</h2>
<p>单源最短路径问题：给定一个带权重的有向图G=(V,E)和权重函数w:E-&gt;R，该权重函数将每条边映射到实数值的权重上。图中一条路径p=&lt;v0,v1,...vk&gt;的权重 w(p)=w(v0,v1)+w(v1,v2)+...+w(v(k-1),vk)。定义结点u到结点v的最短路径权重 delt(u,v)为：</p>
<ul>
<li>min{w(p):u&ndash;&gt;v(通过路径p)}，如果存在一条从结点u到结点v的路径</li>
<li>正无穷 ，如果不存在一条从结点u到结点v的路径</li>
</ul>
<p>从结点u到结点v的最短路径定义为任何一条权重w(p)=delt(u,v)的从u到v的路径p。</p>
<p>给定图G=(V,E)，对每个结点v我们维持一个前驱结点v.pai。在最短路径算法中，由pai值诱导的前驱子图G_pai=(V_pai,E_pai)，其中 V_pai={v属于V:v.pai!=nil}并上源点s， E_pai是V_pai中所有结点的pai值诱导的边的集合：E_pai={(v.pai,v)属于E:v属于V_pai-{s} }。算法终止时，G_pai是一棵最短路径树：该树包含了从源结点s 到每个可以从s到达的结点的一条最短路径。</p>
<p>需要指出的是：最短路径不一定是唯一的，最短路径树叶不一定是唯一的。</p>
<h2>Bellman-Ford算法</h2>
<h3>算法原理</h3>
<p>Bellman-Ford算法解决的是一般情况下的单源最短路径问题。在这里边的权重可以为负值。给定带权的有向图G=(V,E)和权重函数w:E-&gt;R，Bellman-Ford 算法返回一个bool值，表明是否存在一个从源结点可达的权重为负值的环路。若存在这样的一个环路，算法告诉我们不存在解决方案；若不存在这样的环路， 算法将给出最短路径和它们的权重。</p>
<p>Bellman-Ford算法通过对边的松弛操作来渐近的降低从源s到每个结点v的最短路径估计值v.key，直到该估计值与实际的最短路径权重相同为止。</p>
<h3>算法步骤</h3>
<ul>
<li>执行单源最短路径的初始化过程</li>
<li>进行|V|-1次处理，每次处理过程为：对图的每一条边进行一次松弛操作</li>
<li>检查图中是否存在权重为负的环路并返回与之相适应的布尔值</li>
</ul>
<h3>算法性能</h3>
<p>时间复杂度为O(VE) </p>

<p>Definition at line <a class="el" href="bellmanford_8h_source.html#l00143">143</a> of file <a class="el" href="bellmanford_8h_source.html">bellmanford.h</a>.</p>

</div>
</div>
<a class="anchor" id="a8839165b9e3d4c8c2ccac4cdc28aadd5"></a>
<div class="memitem">
<div class="memproto">
<div class="memtemplate">
template&lt;typename GraphType &gt; </div>
      <table class="memname">
        <tr>
          <td class="memname">void IntroductionToAlgorithm::GraphAlgorithm::breadth_first_search </td>
          <td>(</td>
          <td class="paramtype">std::shared_ptr&lt; GraphType &gt;&#160;</td>
          <td class="paramname"><em>graph</em>, </td>
        </tr>
        <tr>
          <td class="paramkey"></td>
          <td></td>
          <td class="paramtype">typename GraphType::VIDType&#160;</td>
          <td class="paramname"><em>source_id</em>, </td>
        </tr>
        <tr>
          <td class="paramkey"></td>
          <td></td>
          <td class="paramtype">std::function&lt; void(typename GraphType::VIDType)&gt;&#160;</td>
          <td class="paramname"><em>pre_action</em> = <code>[](typename&#160;GraphType::VIDType){}</code>, </td>
        </tr>
        <tr>
          <td class="paramkey"></td>
          <td></td>
          <td class="paramtype">std::function&lt; void(typename GraphType::VIDType)&gt;&#160;</td>
          <td class="paramname"><em>post_action</em> = <code>[](typename&#160;GraphType::VIDType){}</code>&#160;</td>
        </tr>
        <tr>
          <td></td>
          <td>)</td>
          <td></td><td></td>
        </tr>
      </table>
</div><div class="memdoc">

<p>breadth_first_search：广度优先搜索，算法导论22章22.2节 </p>
<dl class="params"><dt>Parameters</dt><dd>
  <table class="params">
    <tr><td class="paramname">graph:指向图的强引用，必须非空。若为空则抛出异常</td><td></td></tr>
    <tr><td class="paramname">source_id：广度优先搜索的源点&lt;tt&gt;id&lt;/tt&gt;，必须有效。若无效则抛出异常</td><td></td></tr>
    <tr><td class="paramname">pre_action:一个可调用对象，在每次发现一个顶点时调用，调用参数为该顶点的&lt;tt&gt;id&lt;/tt&gt;。默认为空操作，即不进行任何操作</td><td></td></tr>
    <tr><td class="paramname">post_action:一个可调用对象，在每次对一个顶点搜索完成时调用，调用参数为该顶点的&lt;tt&gt;id&lt;/tt&gt;。默认为空操作，即不进行任何操作</td><td></td></tr>
  </table>
  </dd>
</dl>
<dl class="section return"><dt>Returns</dt><dd>:void</dd></dl>
<p><code>source_id</code>在以下情况下无效：</p>
<ul>
<li><code>source_id</code>不在区间<code>[0,N)</code>之间时，<code>source_id</code>无效</li>
<li><code>graph</code>中不存在某个顶点的<code>id</code>等于<code>source_id</code>时，<code>source_id</code>无效</li>
</ul>
<p>广度优先搜索：该算法维护已经发现结点和未发现结点的边界，沿着其广度方向向外扩展。每个结点有三种颜色：白色、灰色、黑色。 白色结点表示未发现；灰色结点表示已发现但是未处理完成；黑色结点表示已处理完成。其中灰色结点就是边界。</p>
<p>给定图 G=(V,E)和一个可以识别的源点<code>s</code>。。所有的结点在一开始都被涂上白色。每个结点的颜色存放在属性<code>color</code>中； 每个结点的前驱结点放在属性<code>parent</code>中。每个结点的属性<code>key</code>存放的是从源点到本结点的距离。该算法使用一个先进先出的队列Q来管理灰色结点集。</p>
<ul>
<li>将所有结点涂为白色，<code>key</code>属性设置为正无穷，父结点置为空；</li>
<li>将源点涂为灰色，源点前驱设为空，源点的<code>key</code>设为0；</li>
<li>将源点加入队列Q中；Q中存放的都是已发现但是尚未处理完成的结点</li>
<li>循环直到队列Q为空，在循环中执行以下操作：<ul>
<li>取出队列Q头部的结点<code>v</code></li>
<li>对结点<code>v</code>的邻接表中的白色结点进行发现操作，并将这些结点加入队列Q中</li>
<li>对结点<code>v</code>染成黑色；</li>
</ul>
</li>
</ul>
<p>算法的时间复杂度为 O(E+V)</p>
<p>最短路径：广度优先搜索能找出给定源结点s到所有可以到达的结点之间的距离。定义从源s到结点v之间的最短路径距离 delt(s,v) 为从结点s到v之间的所有路径里面最少的边数。 如果从s到v没有路径，则 delt(s,v)=正无穷大 。我们定义从s到v之间的长度为 delt(s,v) 的路径为 s 到 v 的最短路径。可以证明：广度优先搜索可以正确计算出最短路径距离。</p>
<p>广度优先树：对于G=(V,E)和源点s，定义图G的前驱子图为 G_pai=(V_pai,E_pai)，其中 V_pai={ v属于V: v.parent!=NIL}并上{s}，E_pai={(v.parent,v):v属于(V_pai-{s})}。 即V_pai由从源s可达的所有结点组成（包括s本身），E_pai由V_pai中去掉s之后的结点的入边组成，其中该入边的对端为结点的父结点。 BFS算法获取的前驱子图G_pai包含一条从源结点s到结点v的唯一简单路径，而且该路径也是图G里面从源s到v之间的一条最短路径，因此前驱子图也称为广度优先树。 </p>

<p>Definition at line <a class="el" href="bfs_8h_source.html#l00068">68</a> of file <a class="el" href="bfs_8h_source.html">bfs.h</a>.</p>

</div>
</div>
<a class="anchor" id="a31fe8fc6f732112632c51221e739a7d4"></a>
<div class="memitem">
<div class="memproto">
<div class="memtemplate">
template&lt;typename GraphType &gt; </div>
      <table class="memname">
        <tr>
          <td class="memname">void IntroductionToAlgorithm::GraphAlgorithm::connected_component </td>
          <td>(</td>
          <td class="paramtype">std::shared_ptr&lt; GraphType &gt;&#160;</td>
          <td class="paramname"><em>graph</em></td><td>)</td>
          <td></td>
        </tr>
      </table>
</div><div class="memdoc">

<p>connected_component：无向图的连通分量，算法导论21章21.1节 </p>
<dl class="params"><dt>Parameters</dt><dd>
  <table class="params">
    <tr><td class="paramname">graph:指向图的强指针，必须非空。若为空则抛出异常</td><td></td></tr>
  </table>
  </dd>
</dl>
<dl class="section return"><dt>Returns</dt><dd>:void</dd></dl>
<p>connected_component函数使用不相交集合操作来计算一个无向图的连通分量。一旦connected_component函数与处理了该图，same_component 函数就会回答两个顶点是否在同一个连通分量。</p>
<p>connected_component算法步骤：</p>
<ul>
<li>将每个顶点v放入它自己的集合中</li>
<li>对每一条边(u,v)，它将包含u和v的集合进行合并</li>
</ul>
<p>在处理完搜有边之后，两个顶点在相同的连通分量当且仅当与之对应的对象在相同的集合中 </p>

<p>Definition at line <a class="el" href="connectedcomponent_8h_source.html#l00044">44</a> of file <a class="el" href="connectedcomponent_8h_source.html">connectedcomponent.h</a>.</p>

</div>
</div>
<a class="anchor" id="acc8cd65d7cf2d584f86cfd92494bdbf4"></a>
<div class="memitem">
<div class="memproto">
<div class="memtemplate">
template&lt;typename GraphType &gt; </div>
      <table class="memname">
        <tr>
          <td class="memname">std::shared_ptr&lt;GraphType&gt; IntroductionToAlgorithm::GraphAlgorithm::create_Gf </td>
          <td>(</td>
          <td class="paramtype">const std::shared_ptr&lt; GraphType &gt;&#160;</td>
          <td class="paramname"><em>graph</em>, </td>
        </tr>
        <tr>
          <td class="paramkey"></td>
          <td></td>
          <td class="paramtype">std::array&lt; std::array&lt; typename GraphType::EWeightType, GraphType::NUM &gt;, GraphType::NUM &gt; &amp;&#160;</td>
          <td class="paramname"><em>flow</em>&#160;</td>
        </tr>
        <tr>
          <td></td>
          <td>)</td>
          <td></td><td></td>
        </tr>
      </table>
</div><div class="memdoc">

<p>create_Gf：根据指定流网络生成一个残余网络。算法导论26章26.2节 </p>
<dl class="params"><dt>Parameters</dt><dd>
  <table class="params">
    <tr><td class="paramname">graph:指定流网络。它必须非空，否则抛出异常</td><td></td></tr>
    <tr><td class="paramname">flow</td><td>一个流 </td></tr>
  </table>
  </dd>
</dl>
<dl class="section return"><dt>Returns</dt><dd>: 残余网络</dd></dl>
<h2>残余网络</h2>
<p>给定网络G(V,E)和流量f，残余网络Gf(V,Ef)由那些仍有空间对流量进行调整的边构成。Gf中的顶点就是原图G中的顶点。残余网络Gf中的边可以由以下组成：</p>
<ul>
<li>若(u,v)属于E，且f(u,v)&lt;c(u,v)，则存在边(u,v)属于Ef，且cf(u,v)=c(u,v)-f(u,v)，表示沿着该方向图G中还能流通cf大小的流量</li>
<li>若(u,v)属于E，则存在边(v,u)属于Ef,且 cf(v,u)=c(u,v)，表示沿着(u,v)的反方向（即(v,u)方向)可以压入cf大小的反向流量 <blockquote class="doxtable">
<p>这里f(u,v)为边(u,v)上的流；c(u,v)为图G的边(u,v)的容量；cf(u,v)为残余网络Gf上的边(u,v)的容量 </p>
</blockquote>
</li>
</ul>
<p>这里假定容量c&gt;0，一旦容量c=0表示边不存在（禁止流通）；f&gt;=0，表示流是正向的。同时假定图中不存在双向边： 图G中不可能同时存在边(u,v)以及边(v,u)（即管道是单向的）</p>
<p>要求graph的无效权重为0，否则抛出异常</p>
<p>性能：时间复杂度 O(V+E) </p>

<p>Definition at line <a class="el" href="fordfulkerson_8h_source.html#l00054">54</a> of file <a class="el" href="fordfulkerson_8h_source.html">fordfulkerson.h</a>.</p>

</div>
</div>
<a class="anchor" id="ad6a1917551c87991625d8402593ec863"></a>
<div class="memitem">
<div class="memproto">
<div class="memtemplate">
template&lt;typename GraphType &gt; </div>
      <table class="memname">
        <tr>
          <td class="memname"><a class="el" href="struct_introduction_to_algorithm_1_1_graph_algorithm_1_1_list.html">List</a>&lt;<a class="el" href="struct_introduction_to_algorithm_1_1_graph_algorithm_1_1_list_node.html">ListNode</a>&lt;typename GraphType::VertexType&gt; &gt; IntroductionToAlgorithm::GraphAlgorithm::create_L </td>
          <td>(</td>
          <td class="paramtype">std::shared_ptr&lt; GraphType &gt;&#160;</td>
          <td class="paramname"><em>graph</em>, </td>
        </tr>
        <tr>
          <td class="paramkey"></td>
          <td></td>
          <td class="paramtype">typename GraphType::VIDType&#160;</td>
          <td class="paramname"><em>src</em>, </td>
        </tr>
        <tr>
          <td class="paramkey"></td>
          <td></td>
          <td class="paramtype">typename GraphType::VIDType&#160;</td>
          <td class="paramname"><em>dst</em>&#160;</td>
        </tr>
        <tr>
          <td></td>
          <td>)</td>
          <td></td><td></td>
        </tr>
      </table>
</div><div class="memdoc">

<p>create_L：前置重贴标签算法中的创建L链表操作 </p>
<dl class="params"><dt>Parameters</dt><dd>
  <table class="params">
    <tr><td class="paramname">graph:指定流网络。它必须非空，否则抛出异常</td><td></td></tr>
    <tr><td class="paramname">src</td><td>流的源点，必须有效否则抛出异常 </td></tr>
    <tr><td class="paramname">dst</td><td>流的汇点，必须有效否则抛出异常 </td></tr>
  </table>
  </dd>
</dl>
<dl class="section return"><dt>Returns</dt><dd>: 初始化的L链表</dd></dl>
<p>如果src、dst任何一个顶点无效，则抛出异常：</p>
<ul>
<li>如果指定的顶点<code>id</code>不在<code>[0,N)</code>之间，则无效</li>
<li>如果不存在某个顶点与指定的顶点<code>id</code>相同，则无效</li>
</ul>
<p>该操作将所有的除s、t之外的顶点加入到L链表中 </p>

<p>Definition at line <a class="el" href="relabeltofront_8h_source.html#l00113">113</a> of file <a class="el" href="relabeltofront_8h_source.html">relabeltofront.h</a>.</p>

</div>
</div>
<a class="anchor" id="aec7fe196e6aee4c8e6004a05495c8813"></a>
<div class="memitem">
<div class="memproto">
<div class="memtemplate">
template&lt;typename GraphType &gt; </div>
      <table class="memname">
        <tr>
          <td class="memname">void IntroductionToAlgorithm::GraphAlgorithm::dag_shortest_path </td>
          <td>(</td>
          <td class="paramtype">std::shared_ptr&lt; GraphType &gt;&#160;</td>
          <td class="paramname"><em>graph</em>, </td>
        </tr>
        <tr>
          <td class="paramkey"></td>
          <td></td>
          <td class="paramtype">typename GraphType::VIDType&#160;</td>
          <td class="paramname"><em>source_id</em>&#160;</td>
        </tr>
        <tr>
          <td></td>
          <td>)</td>
          <td></td><td></td>
        </tr>
      </table>
</div><div class="memdoc">

<p>dag_shortest_path：有向无环图的单源最短路径的dag_shortest_path算法，算法导论24章24.2节 </p>
<dl class="params"><dt>Parameters</dt><dd>
  <table class="params">
    <tr><td class="paramname">graph:指向图的强指针，必须非空。若为空则抛出异常</td><td></td></tr>
    <tr><td class="paramname">source_id：最小生成树的根结点&lt;tt&gt;id&lt;/tt&gt;，必须有效。若无效则抛出异常</td><td></td></tr>
  </table>
  </dd>
</dl>
<dl class="section return"><dt>Returns</dt><dd>: void</dd></dl>
<h2>单源最短路径</h2>
<p>单源最短路径问题：给定一个带权重的有向图G=(V,E)和权重函数w:E-&gt;R，该权重函数将每条边映射到实数值的权重上。图中一条路径p=&lt;v0,v1,...vk&gt;的权重 w(p)=w(v0,v1)+w(v1,v2)+...+w(v(k-1),vk)。定义结点u到结点v的最短路径权重 delt(u,v)为：</p>
<ul>
<li>min{w(p):u&ndash;&gt;v(通过路径p)}，如果存在一条从结点u到结点v的路径</li>
<li>正无穷 ，如果不存在一条从结点u到结点v的路径</li>
</ul>
<p>从结点u到结点v的最短路径定义为任何一条权重w(p)=delt(u,v)的从u到v的路径p。</p>
<p>给定图G=(V,E)，对每个结点v我们维持一个前驱结点v.pai。在最短路径算法中，由pai值诱导的前驱子图G_pai=(V_pai,E_pai)，其中 V_pai={v属于V:v.pai!=nil}并上源点s， E_pai是V_pai中所有结点的pai值诱导的边的集合：E_pai={(v.pai,v)属于E:v属于V_pai-{s} }。算法终止时，G_pai是一棵最短路径树：该树包含了从源结点s 到每个可以从s到达的结点的一条最短路径。</p>
<p>需要指出的是：最短路径不一定是唯一的，最短路径树叶不一定是唯一的。</p>
<h2>dag_shortest_path算法</h2>
<h3>算法原理</h3>
<p>dag_shortest_path算法解决的是有向无环图中的单源最短路径问题。在有向无环图中不存在环路因此也就不存在权重为负值的环路，最短路径都是存在的。 dag_shortest_path根据结点的拓扑排序次数来对带权重的有向无环图进行边的松弛操作，可以再O(V+E)时间内计算出单源最短路径。</p>
<h3>算法步骤</h3>
<ul>
<li>对有向无环图进行拓扑排序</li>
<li>执行单源最短路径的初始化过程</li>
<li>按照顶点的拓扑排序的顺序依次处理，每次处理过程为：对该顶点出发的每一条边进行一次松弛操作</li>
</ul>
<h3>算法性能</h3>
<p>时间复杂度为O(V+E) </p>

<p>Definition at line <a class="el" href="dagshortpath_8h_source.html#l00071">71</a> of file <a class="el" href="dagshortpath_8h_source.html">dagshortpath.h</a>.</p>

</div>
</div>
<a class="anchor" id="a9f44099f26242f50087b3cc16dff965f"></a>
<div class="memitem">
<div class="memproto">
<div class="memtemplate">
template&lt;typename GraphType &gt; </div>
      <table class="memname">
        <tr>
          <td class="memname">void IntroductionToAlgorithm::GraphAlgorithm::depth_first_search </td>
          <td>(</td>
          <td class="paramtype">std::shared_ptr&lt; GraphType &gt;&#160;</td>
          <td class="paramname"><em>graph</em>, </td>
        </tr>
        <tr>
          <td class="paramkey"></td>
          <td></td>
          <td class="paramtype">std::function&lt; void(typename GraphType::VIDType, int)&gt;&#160;</td>
          <td class="paramname"><em>pre_action</em> = <code>[](typename&#160;GraphType::VIDType,int){}</code>, </td>
        </tr>
        <tr>
          <td class="paramkey"></td>
          <td></td>
          <td class="paramtype">std::function&lt; void(typename GraphType::VIDType, int)&gt;&#160;</td>
          <td class="paramname"><em>post_action</em> = <code>[](typename&#160;GraphType::VIDType,int){}</code>, </td>
        </tr>
        <tr>
          <td class="paramkey"></td>
          <td></td>
          <td class="paramtype">std::function&lt; void(typename GraphType::VIDType, int)&gt;&#160;</td>
          <td class="paramname"><em>pre_root_action</em> = <code>[](typename&#160;GraphType::VIDType,int){}</code>, </td>
        </tr>
        <tr>
          <td class="paramkey"></td>
          <td></td>
          <td class="paramtype">std::function&lt; void(typename GraphType::VIDType, int)&gt;&#160;</td>
          <td class="paramname"><em>post_root_action</em> = <code>[](typename&#160;GraphType::VIDType,int){}</code>, </td>
        </tr>
        <tr>
          <td class="paramkey"></td>
          <td></td>
          <td class="paramtype">const std::vector&lt; typename GraphType::VIDType &gt; &amp;&#160;</td>
          <td class="paramname"><em>search_order</em> = <code>std::vector&lt;typename&#160;GraphType::VIDType&gt;()</code>&#160;</td>
        </tr>
        <tr>
          <td></td>
          <td>)</td>
          <td></td><td></td>
        </tr>
      </table>
</div><div class="memdoc">

<p>depth_first_search：深度优先搜索，算法导论22章22.3节 </p>
<dl class="params"><dt>Parameters</dt><dd>
  <table class="params">
    <tr><td class="paramname">graph:指向图的强引用，必须非空。若为空则抛出异常</td><td></td></tr>
    <tr><td class="paramname">pre_root_action:一个可调用对象，在每次发现一个顶点且该顶点是深度优先森林的根节点时调用，调用参数为该顶点的&lt;tt&gt;id&lt;/tt&gt;以及发现时间&lt;tt&gt;time&lt;/tt&gt;。默认为空操作，即不进行任何操作</td><td></td></tr>
    <tr><td class="paramname">post_root_action:一个可调用对象，在每次对一个顶点搜索完成时且该顶点是深度优先森林的根节点时调用调用，调用参数为该顶点的&lt;tt&gt;id&lt;/tt&gt;以及发现时间&lt;tt&gt;time&lt;/tt&gt;。默认为空操作，即不进行任何操作</td><td></td></tr>
    <tr><td class="paramname">pre_action:一个可调用对象，在每次发现一个顶点时调用，调用参数为该顶点的&lt;tt&gt;id&lt;/tt&gt;以及发现时间&lt;tt&gt;time&lt;/tt&gt;。默认为空操作，即不进行任何操作</td><td></td></tr>
    <tr><td class="paramname">post_action:一个可调用对象，在每次对一个顶点搜索完成时调用，调用参数为该顶点的&lt;tt&gt;id&lt;/tt&gt;以及发现时间&lt;tt&gt;time&lt;/tt&gt;。默认为空操作，即不进行任何操作</td><td></td></tr>
    <tr><td class="paramname">search_order:指定搜索顶点的顺序（不同的搜索顺序可能形成的深度优先森林不同)，如果为空则按照顶点的&lt;tt&gt;id&lt;/tt&gt;顺序。默认为空</td><td></td></tr>
  </table>
  </dd>
</dl>
<dl class="section return"><dt>Returns</dt><dd>:void</dd></dl>
<p>深度优先搜索：深度优先搜索总是对最近才发现的结点v的出发边进行搜索，直到该结点的所有出发边都被发现为止。一旦结点v的所有出发边都被发现，则“回溯”到v的前驱结点（v是经过该结点才被发现的）。 该过程一直持续到源结点可以达到的所有结点都被发现为止。如果还存在尚未发现的结点，则深度优先搜索将从这些未被发现的结点中任选一个作为新的源结点，并重复同样的搜索过程。该算法重复整个过程， 直到图中的所有结点被发现为止。</p>
<p>深度优先搜索维护一个全局的时间。每个结点v有两个时间戳，discover_time记录了v第一次被发现的时间（v涂上灰色的时刻）；finish_time记录了搜索完成v的相邻结点的时间（v涂上黑色的时刻）。 结点v在v.discover_time之前为白色，在v.discover_time之后与v.finish_time之前为灰色，在v.finish_time之后为黑色</p>
<p>深度优先搜索步骤：</p>
<ul>
<li>初始化：将所有结点染白色，并将它们的父结点置为空(由于DFS_Vertex构造函数将结点color设为白色，且将父结点置为空，因此在本算法中这个步骤可以省略)</li>
<li>将全局时间 time 置为0</li>
<li>遍历结点集V，取出结点v -若v是白色的（尚未发现），则调用 visit 操作 <blockquote class="doxtable">
<p>当这里调用 visit 操作时，结点v会成为一棵树的根</p>
<p>深度优先搜索的结果会依赖于遍历结点集V的顺序。不同的遍历顺序得到的结果会不同 </p>
</blockquote>
</li>
</ul>
<p>深度优先搜索性能：时间复杂度 O(V+E)</p>
<p>深度优先搜索的性质：证明请参考《算法导论》:</p>
<ul>
<li>深度优先搜索生成的前驱子图G_pai是一个由多棵树构成的森林</li>
<li>结点 v 是结点 u 在深度优先森林中的后代当且仅当结点v在结点u为灰色的时间段内被发现</li>
<li>结点的发现时间和完成时间具有括号化结构：如果以左括号"(u"来表示结点u被发现，以后括号"u)"表示结点u完成。则发现和完成的历史记载会形成一个规整的表达式。 在深度优先搜索中，对于任意两个结点u和v来说，下面三种情况只有一种成立<ul>
<li>区间[u.discover_time,u.finish_time]与区间[v.discover_time,v.finish_time]完全分离。 此时在深度优先森林中，结点u不是结点v的后代，结点v也不是结点u的后代</li>
<li>区间[u.discover_time,u.finish_time]完全包含在[v.discover_time,v.finish_time]，此时在深度优先森林中，结点u是结点v的后代</li>
<li>区间[v.discover_time,v.finish_time]完全包含在[u.discover_time,u.finish_time]，此时在深度优先森林中，结点v是结点u的后代</li>
</ul>
</li>
</ul>
<p>深度优先森林的边：对于在图G上运行深度优先搜索算法所生成的深度优先森林G_pai，可以定义四种类型的边：</p>
<ul>
<li>树边：它是深度优先森林的边。若结点v是因深度优先算法对边(u,v)的搜索而首先被发现，则(u,v)是一条树边</li>
<li>后向边： 后向边(u,v)将结点u连接到其深度优先树中某个祖先结点v。对于有向图的自循环，自循环被认为是后向边</li>
<li>前向边： 将结点u连接到其在深度优先树中一个后代结点v</li>
<li>横向边： 其他的边。这些边可以连接同一棵深度优先树中的结点（只要其中一个结点不是另外一个结点的祖先），也可以连接不同深度优先树中的两个结点。</li>
</ul>
<p>在深度优先搜索中，当第一次搜索边(u,v)时：</p>
<ul>
<li>若结点v为白色，表明边(u,v)是一条树边</li>
<li>若结点v为灰色，表明边(u,v)是一条后向边</li>
<li>若结点v为黑色，表明边(u,v)是一条前向边或者横向边<ul>
<li>在 u.discover_time&lt; v.discover_time 时，为前向边</li>
<li>在 u.discover_time&lt; v.discover_time 时，为横向边</li>
</ul>
</li>
</ul>
<p>在无向图中，每条边要么是树边，要么是后向边。从来不会出现前向边和横向边。 </p>

<p>Definition at line <a class="el" href="dfs_8h_source.html#l00138">138</a> of file <a class="el" href="dfs_8h_source.html">dfs.h</a>.</p>

</div>
</div>
<a class="anchor" id="acac554e111d6377c630865258dd6aa19"></a>
<div class="memitem">
<div class="memproto">
<div class="memtemplate">
template&lt;typename GraphType &gt; </div>
      <table class="memname">
        <tr>
          <td class="memname">void IntroductionToAlgorithm::GraphAlgorithm::dijkstra </td>
          <td>(</td>
          <td class="paramtype">std::shared_ptr&lt; GraphType &gt;&#160;</td>
          <td class="paramname"><em>graph</em>, </td>
        </tr>
        <tr>
          <td class="paramkey"></td>
          <td></td>
          <td class="paramtype">typename GraphType::VIDType&#160;</td>
          <td class="paramname"><em>source_id</em>&#160;</td>
        </tr>
        <tr>
          <td></td>
          <td>)</td>
          <td></td><td></td>
        </tr>
      </table>
</div><div class="memdoc">

<p>dijkstra：单源最短路径的dijkstra算法，算法导论24章24.3节 </p>
<dl class="params"><dt>Parameters</dt><dd>
  <table class="params">
    <tr><td class="paramname">graph:指向图的强指针，必须非空。若为空则抛出异常</td><td></td></tr>
    <tr><td class="paramname">source_id：最小生成树的根结点&lt;tt&gt;id&lt;/tt&gt;，必须有效。若无效则抛出异常</td><td></td></tr>
  </table>
  </dd>
</dl>
<dl class="section return"><dt>Returns</dt><dd>: void</dd></dl>
<h2>单源最短路径</h2>
<p>单源最短路径问题：给定一个带权重的有向图G=(V,E)和权重函数w:E-&gt;R，该权重函数将每条边映射到实数值的权重上。图中一条路径p=&lt;v0,v1,...vk&gt;的权重 w(p)=w(v0,v1)+w(v1,v2)+...+w(v(k-1),vk)。定义结点u到结点v的最短路径权重 delt(u,v)为：</p>
<ul>
<li>min{w(p):u&ndash;&gt;v(通过路径p)}，如果存在一条从结点u到结点v的路径</li>
<li>正无穷 ，如果不存在一条从结点u到结点v的路径</li>
</ul>
<p>从结点u到结点v的最短路径定义为任何一条权重w(p)=delt(u,v)的从u到v的路径p。</p>
<p>给定图G=(V,E)，对每个结点v我们维持一个前驱结点v.pai。在最短路径算法中，由pai值诱导的前驱子图G_pai=(V_pai,E_pai)，其中 V_pai={v属于V:v.pai!=nil}并上源点s， E_pai是V_pai中所有结点的pai值诱导的边的集合：E_pai={(v.pai,v)属于E:v属于V_pai-{s} }。算法终止时，G_pai是一棵最短路径树：该树包含了从源结点s 到每个可以从s到达的结点的一条最短路径。</p>
<p>需要指出的是：最短路径不一定是唯一的，最短路径树叶不一定是唯一的。</p>
<h2>Dijkstra算法</h2>
<h3>算法原理</h3>
<p>Dijkstra算法解决的是有向图中的单源最短路径问题。Dijkstra算法要求所有边的权重都为非负值。</p>
<p>Dijkstra算法核心信息是一组结点集合 S 。从源结点s 到集合 S 中的每一个结点之间的最短路径已经被找到。算法重复从结点集合 V-S 中选择最短路径估计最小的结点u, 将u加入到集合S中，然后对所有从u出发的边进行松弛。本算法利用最小优先队列Q来保存结点集合，每个结点的关键字为它的key值。</p>
<h3>算法步骤</h3>
<ul>
<li>调用 <code>initialize_single_source</code>函数对图的顶点进行初始化</li>
<li>将集合S置为空，将所有顶点放入最小优先队列Q</li>
<li>循环操作直到Q为空，循环内执行以下操作：<ul>
<li>弹出最小优先级队列队首元素u</li>
<li>将u对应的结点放入集合S中</li>
<li>对从u出发的边且另一端在Q中的边进行松弛。松弛过程隐含着Q的一个<code>decreate_key()</code>方法的调用</li>
</ul>
</li>
</ul>
<h3>算法性能</h3>
<p>时间复杂度为O(V^2+E) </p>

<p>Definition at line <a class="el" href="dijkstra_8h_source.html#l00077">77</a> of file <a class="el" href="dijkstra_8h_source.html">dijkstra.h</a>.</p>

</div>
</div>
<a class="anchor" id="a2ae42c12c93664d94b5a6f9980fe8540"></a>
<div class="memitem">
<div class="memproto">
<div class="memtemplate">
template&lt;typename GraphType &gt; </div>
      <table class="memname">
        <tr>
          <td class="memname">void IntroductionToAlgorithm::GraphAlgorithm::discharge </td>
          <td>(</td>
          <td class="paramtype">std::shared_ptr&lt; GraphType &gt;&#160;</td>
          <td class="paramname"><em>graph</em>, </td>
        </tr>
        <tr>
          <td class="paramkey"></td>
          <td></td>
          <td class="paramtype">typename GraphType::VIDType&#160;</td>
          <td class="paramname"><em>u_id</em>, </td>
        </tr>
        <tr>
          <td class="paramkey"></td>
          <td></td>
          <td class="paramtype">std::array&lt; std::array&lt; typename GraphType::EWeightType, GraphType::NUM &gt;, GraphType::NUM &gt; &amp;&#160;</td>
          <td class="paramname"><em>flow</em>&#160;</td>
        </tr>
        <tr>
          <td></td>
          <td>)</td>
          <td></td><td></td>
        </tr>
      </table>
</div><div class="memdoc">

<p>discharge：最大流的前置重贴标签算法中的释放操作。算法导论26章26.5节 </p>
<dl class="params"><dt>Parameters</dt><dd>
  <table class="params">
    <tr><td class="paramname">graph:指定流网络。它必须非空，否则抛出异常</td><td></td></tr>
    <tr><td class="paramname">u_id</td><td>图的顶点id，必须有效否则抛出异常 </td></tr>
    <tr><td class="paramname">flow</td><td>预流 </td></tr>
  </table>
  </dd>
</dl>
<dl class="section return"><dt>Returns</dt><dd>: void</dd></dl>
<p>如果顶点无效，则抛出异常：</p>
<ul>
<li>如果指定的顶点<code>id</code>不在<code>[0,N)</code>之间，则无效</li>
<li>如果不存在某个顶点与指定的顶点<code>id</code>相同，则无效</li>
</ul>
<p>对于溢出结点u,如果将其所有多余的流通过许可边推送到相邻的结点上，则称该结点得到释放。 在释放过程中，需要对结点u进行重贴标签操作，这使得从结点u发出的边成为许可边。discharge(u) 操作步骤如下：</p>
<ul>
<li>循环，条件为u.e&gt;0，循环内操作为：<ul>
<li>获取u.current，假设为v</li>
<li>如果v为空，即遍历到u.N链表的末尾，则对u执行relabel操作，然后将u.current指向u.N链表的头部</li>
<li>如果 v非空，且满足 push 操作的条件(c_f(u,v)&gt;0且 u.h=v.h+1)，则执行push操作</li>
<li>如果 v 非空，但不满足 push 操作，则 u.current指向u.N链表的下一个结点 </li>
</ul>
</li>
</ul>

<p>Definition at line <a class="el" href="relabeltofront_8h_source.html#l00053">53</a> of file <a class="el" href="relabeltofront_8h_source.html">relabeltofront.h</a>.</p>

</div>
</div>
<a class="anchor" id="a680307505286ae3230d1843c342e874e"></a>
<div class="memitem">
<div class="memproto">
<div class="memtemplate">
template&lt;typename MatrixType &gt; </div>
      <table class="memname">
        <tr>
          <td class="memname">MatrixType IntroductionToAlgorithm::GraphAlgorithm::extend_path </td>
          <td>(</td>
          <td class="paramtype">const MatrixType &amp;&#160;</td>
          <td class="paramname"><em>L</em>, </td>
        </tr>
        <tr>
          <td class="paramkey"></td>
          <td></td>
          <td class="paramtype">const MatrixType &amp;&#160;</td>
          <td class="paramname"><em>W</em>&#160;</td>
        </tr>
        <tr>
          <td></td>
          <td>)</td>
          <td></td><td></td>
        </tr>
      </table>
</div><div class="memdoc">

<p>extend_path：扩展一条边，算法导论25章25.1节 </p>
<dl class="params"><dt>Parameters</dt><dd>
  <table class="params">
    <tr><td class="paramname">L:初始L矩阵</td><td></td></tr>
    <tr><td class="paramname">W</td><td>图的权重矩阵 </td></tr>
  </table>
  </dd>
</dl>
<dl class="section return"><dt>Returns</dt><dd>: 扩展之后的L矩阵</dd></dl>
<p>该函数作为 matrix_shortest_path 的辅助函数 &gt;这里要求 MatrixType是一个n*n的矩阵。如果MatrixType不是一个n*n的矩阵，则编译失败</p>
<p>算法步骤如下：</p>
<ul>
<li>外层循环 i 从 0...N-1(N次)<ul>
<li>内层循环 j 从 0...N-1(N次)<ul>
<li>将newL[i][j]设为正无穷，对所有的k,k 从 0...N-1(N次)，选取 L[i][k]+W[k][j]的最小值赋值给newL[i][j]</li>
</ul>
</li>
</ul>
</li>
<li>最终返回 newL</li>
</ul>
<p>性能：时间复杂度 O(n^3) </p>

<p>Definition at line <a class="el" href="matrix__shortest__path_8h_source.html#l00048">48</a> of file <a class="el" href="matrix__shortest__path_8h_source.html">matrix_shortest_path.h</a>.</p>

</div>
</div>
<a class="anchor" id="ab951caca0797ff2907a180fe81609c70"></a>
<div class="memitem">
<div class="memproto">
<div class="memtemplate">
template&lt;typename GraphType &gt; </div>
      <table class="memname">
        <tr>
          <td class="memname">std::pair&lt; std::array&lt;std::array&lt;typename GraphType::EWeightType ,GraphType::NUM&gt;,GraphType::NUM&gt;, std::array&lt;std::array&lt;typename GraphType::EWeightType ,GraphType::NUM&gt;,GraphType::NUM&gt; &gt; IntroductionToAlgorithm::GraphAlgorithm::floyd_warshall </td>
          <td>(</td>
          <td class="paramtype">std::shared_ptr&lt; GraphType &gt;&#160;</td>
          <td class="paramname"><em>graph</em></td><td>)</td>
          <td></td>
        </tr>
      </table>
</div><div class="memdoc">

<p>floyd_warshall：返回所有节点对的最短路径的floyd_warshall算法。算法导论25章25.2节 </p>
<dl class="params"><dt>Parameters</dt><dd>
  <table class="params">
    <tr><td class="paramname">graph:指定的有向图。它必须非空，否则抛出异常</td><td></td></tr>
  </table>
  </dd>
</dl>
<dl class="section return"><dt>Returns</dt><dd>: 一个n*n的矩阵(d_i_j)与n*n的矩阵(p_i_j)的std::pair，其中 d_i_j 代表的是结点i到j的一条最短路径的权重, p_i_j 为从结点i到j的一条最短路径上j的前驱结点</dd></dl>
<h2>所有结点对的最短路径</h2>
<p>给定一个带权重的有向图G=(V,E)，其权重函数为w:E-&gt;R，该函数将边映射到实值权重上。我们希望找到对于所有的结点对u,v属于V，找出一条从结点u 到结点v的最短路径，以及这条路径的权重。</p>
<p>与单源最短路径不同中使用邻接表来表示图不同，本章的多数算法使用邻接矩阵来表示图。该矩阵代表的是一个有n个结点的有向图G=(V,E)的边的权重W=(w_i_j)， 其中 w_i_j =:</p>
<ul>
<li>0:若i=j</li>
<li>有向边(i,j)的权重，若i!=j且(i,j)属于E</li>
<li>正无穷，若 i!=j且(i,j)不属于E</li>
</ul>
<p>我们允许存在负权重的边，目前仍然假定图中不存在权重为负值的环路。</p>
<p>本章讨论的所有结点对最短路径的算法的输出也是一个n*n的矩阵D=(d_i_j)，其中 d_i_j 代表的是结点i到j的一条最短路径的权重。</p>
<p>有时候为了解决所有结点对最短路径问题，我们不仅要计算出最短路径权重，还需要计算出前驱结点矩阵 II=(pai_i_j)，其中 pai_i_j在i=j或者从i到j 不存在路径时为NIL，在其他情况下给出的是从结点i到结点j的某条最短路径上结点j的前驱结点。由矩阵II的第i行所诱导的子图应当是一棵根节点为i 的最短路径树。</p>
<h2>floyd_warshall 算法</h2>
<h3>算法原理</h3>
<p>floyd_warshall也是采用一种动态规划算法来解决问题。假定图G中的所有结点为V={1,2,3...n},考虑其中的一个子集{1,2,...k}，这里k是某个小于n的整数。 图中可以存在负权重的边，但是不能存在权重为负的环路。对于任意结点对i,j属于V，考虑从结点i到结点j的所有中间结点均取自集合{1,2,...k}的路径，并且假设p为其中权重最小的路径。</p>
<ul>
<li>若结点k不是路径p的中间结点，则路径p上的所有中间结点都属于集合{1,2,3,...k-1}。则结点i到j的中间结点取自集合{1,2,...k-1} 的一条最短路径也是从结点i到j的中间结点取自{1,2...k)的一条最短路径</li>
<li>若结点k是路径p上的中间结点，则路径p分解为 i&ndash;&gt;k(经过p1)&ndash;&gt;j(经过p2)，则路径p1是结点i到k的中间结点取自集合{1,2...k-1} 的一条最短路径。路径p2是结点k到j的中间结点取自集合{1,2,...k-1}的一条最短路径。</li>
</ul>
<p>根据以上观测，设d_i_j&lt;k&gt;为从结点i到结点j的所有中间结点全部取自集合{1,2...k}的一条最短路径的权重。当k=0时，从结点i到j 的一条不包含编号大于0的中间结点的路径将没有任何中间结点。这样的路径最多只有一条边，因此d_i_j&lt;0&gt;=w_i_j。因此d_i_j&lt;k&gt;为：</p>
<ul>
<li>w_i_j：当k=0</li>
<li>min(d_i_j&lt;k-1&gt;,d_i_k&lt;k-1&gt;+d_k_j&lt;k-1&gt;：当k&gt;0</li>
</ul>
<p>对任何路径来说，所有中间结点都属于集合{1,2,...n}，则矩阵D&lt;n&gt;=(d_i_j&lt;n&gt;)</p>
<p>我们可以在计算矩阵D&lt;k&gt;的同时计算出前驱矩阵II，即计算一个矩阵序列 II&lt;0&gt;,II&lt;1&gt;...II&lt;k&gt;。这里定义II&lt;k&gt;=(pai_i_j&lt;k&gt;)， pai_i_j&lt;k&gt;为从结点i到j的一条所有中间结点都取自集合{1,2,...k}的最短路径上j的前驱结点。</p>
<p>当k=0时，从i到j的一条最短路径没有中间结点，因此 pai_i_j&lt;0&gt;=:</p>
<ul>
<li>null:若i=j或者w_i_j=正无穷</li>
<li>i ：若i!=j且w_i_j!=正无穷</li>
</ul>
<p>对于 k&gt;=1，若结点k不是路径p的中间结点，则路径p上的所有中间结点都属于集合{1,2,3,...k-1}，则 pai_i_j&lt;k&gt;=pai_i_j&lt;k-1&gt;; 若结点k是路径p的中间结点,考虑路径 i&ndash;&gt;k&ndash;&gt;j，这里 k!=j，则pai_i_j&lt;k&gt;=pai_k_j&lt;k-1&gt;。因此当k&gt;=1时，pai_i_j&lt;k&gt;=:</p>
<ul>
<li>pai_i_j&lt;k-1&gt;：当d_i_j&lt;k-1&gt; &lt;= d_i_k&lt;k-1&gt;+dk_j&lt;k-1&gt;</li>
<li>pai_k_j&lt;k-1&gt;: 当 d_i_j&lt;k-1&gt; &gt; d_i_k&lt;k-1&gt;+dk_j&lt;k-1&gt;</li>
</ul>
<h3>算法步骤</h3>
<ul>
<li>初始化：从图中获取结果矩阵D，以及父矩阵P</li>
<li>外层循环 k 从 0..N-1(N次)<ul>
<li>新建 D&lt;k&gt;,P&lt;k&gt;，同时执行内层循环 i 从 0..N-1(N次)</li>
<li>执行最内层循环 j 从 0..N-1(N次)<ul>
<li>根据递推公式对d_i_j&lt;k&gt;和p_i_j&lt;k&gt;赋值(此时D等于D&lt;k-1&gt;，P等于P&lt;k-1&gt;</li>
</ul>
</li>
<li>将D&lt;k&gt;赋值给D,P&lt;k&gt;赋值给P</li>
</ul>
</li>
<li>返回 std::make_pair(D,P)</li>
</ul>
<h3>算法性能</h3>
<p>时间复杂度 O(V^3) </p>

<p>Definition at line <a class="el" href="floyd__warshall_8h_source.html#l00109">109</a> of file <a class="el" href="floyd__warshall_8h_source.html">floyd_warshall.h</a>.</p>

</div>
</div>
<a class="anchor" id="a23a29754883e1edd7bd95a76634444a2"></a>
<div class="memitem">
<div class="memproto">
<div class="memtemplate">
template&lt;typename GraphType &gt; </div>
      <table class="memname">
        <tr>
          <td class="memname">std::array&lt;std::array&lt;typename GraphType::EWeightType,GraphType::NUM&gt;,GraphType::NUM&gt; IntroductionToAlgorithm::GraphAlgorithm::ford_fulkerson </td>
          <td>(</td>
          <td class="paramtype">const std::shared_ptr&lt; GraphType &gt;&#160;</td>
          <td class="paramname"><em>graph</em>, </td>
        </tr>
        <tr>
          <td class="paramkey"></td>
          <td></td>
          <td class="paramtype">typename GraphType::VIDType&#160;</td>
          <td class="paramname"><em>src</em>, </td>
        </tr>
        <tr>
          <td class="paramkey"></td>
          <td></td>
          <td class="paramtype">typename GraphType::VIDType&#160;</td>
          <td class="paramname"><em>dst</em>&#160;</td>
        </tr>
        <tr>
          <td></td>
          <td>)</td>
          <td></td><td></td>
        </tr>
      </table>
</div><div class="memdoc">

<p>ford_fulkerson：最大流的ford_fulkerson算法。算法导论26章26.2节 </p>
<dl class="params"><dt>Parameters</dt><dd>
  <table class="params">
    <tr><td class="paramname">graph:指定流网络。它必须非空，否则抛出异常</td><td></td></tr>
    <tr><td class="paramname">src</td><td>流的源点，必须有效否则抛出异常 </td></tr>
    <tr><td class="paramname">dst</td><td>流的汇点，必须有效否则抛出异常 </td></tr>
  </table>
  </dd>
</dl>
<dl class="section return"><dt>Returns</dt><dd>: 最大流矩阵</dd></dl>
<p>如果src、dst任何一个顶点无效，则抛出异常：</p>
<ul>
<li>如果指定的顶点<code>id</code>不在<code>[0,N)</code>之间，则无效</li>
<li>如果不存在某个顶点与指定的顶点<code>id</code>相同，则无效</li>
</ul>
<h2>最大流</h2>
<p>流网络G=（V,E）是一个有向图，图中每条边(u,v)属于E都有一个正的容量值c(u,v)&gt;0。而且如果边集合E中包含一条边(u,v)，则图中不存在反向边 (v,u)。为方便起见，假设(u,v)不属于E,定义c(u,v)=0（即无效权重为0），并且在图中不允许自循环。</p>
<p>在流网络中存在两个特殊点：源结点s和汇点t。假定每一个结点都在从源点s到汇点t的某条路径上。即对于每个结点v属于E，存在某条路径 s&ndash;&gt;v&ndash;&gt;t。</p>
<p>G中的流是一个实值函数f:V*V&ndash;&gt;R，满足下面两条性质：</p>
<ul>
<li>容量限制：对于所有结点u,v属于V，要求0&lt;= f(u,v) &lt;= c(u,v)</li>
<li>流量守恒： 对于所有结点u属于V-{s,t}，要求：从u进入的流等于从u出去的流</li>
</ul>
<p>对于(u,v)不属于E的情况，从结点u到v之间没有流，因此f(u,v)=0。我们称非负数值f(u,v)为从结点u到v的流。一个流f的值 |f|=从源点流出的总流量- 流入源结点的总流量</p>
<p>最大流问题：给定流网络G、一个源结点s、一个汇点t,找出值最大的一个流</p>
<h2>ford_fulkerson算法</h2>
<h3>算法原理</h3>
<p>ford_fulkerson 算法更准确的称呼是一种方法而不是算法，因为它包含了几种运行时间各不相同的具体实现。 它依赖于三种重要思想：残余网络、增广路径和切割。</p>
<h4>残余网络</h4>
<p>给定流网络G(V,E)和流量f，残余网络Gf(V,Ef)由那些仍有空间对流量进行调整的边构成。 Gf中的顶点就是原图G中的顶点。残余网络Gf中的边可以由以下组成：</p>
<ul>
<li>若(u,v)属于E，且f(u,v)&lt;c(u,v)，则存在边(u,v)属于Ef，且cf(u,v)=c(u,v)-f(u,v)，表示沿着该方向图G中还能流通cf大小的流量</li>
<li>若(u,v)属于E，则存在边(v,u)属于Ef,且 cf(v,u)=c(u,v)，表示沿着(u,v)的反方向（即(v,u)方向)可以压入cf大小的反向流量 <blockquote class="doxtable">
<p>这里f(u,v)为边(u,v)上的流；c(u,v)为图G的边(u,v)的容量；cf(u,v)为残余网络Gf上的边(u,v)的容量 </p>
</blockquote>
</li>
</ul>
<h4>增广路径</h4>
<p>给定流网络G=(V,E)和流f，增广路径p是残余网络Gf中一条源结点s到汇点t的简单路径。我们称一条增广路径 p上能够为每条边增加的流量的最大值为路径p的残余容量，定义为 cf(p)= min {cf(u,v):(u,v)属于路径p}</p>
<h4>最大流和最小切割定理</h4>
<p>流网络G=(V,E)的一个切割(S,T)是将结点集合V划分为S和T=V-S两个集合，使得s属于S，t属于T。切割(S,T) 的容量c(S,T)=c(u,v)的累加，其中u属于S,v属于T</p>
<p>设f为流网络G=(V,E)中的一个流，该流网络的源点为s，汇点为t，则下面的条件是等价的：</p>
<ul>
<li>f是G的一个最大流</li>
<li>残余网络Gf不包括任何增广路径</li>
<li>|f|=c(S,T)，其中(S,T)是流网络G的某个切割</li>
</ul>
<h3>算法步骤</h3>
<p>ford_fulkerson算法循环增加流的值。在开始的时候对于所有的结点u,v属于V，f(u,v)=0。在每一轮迭代中， 我们将图G的流值进行增加，方法就是在G的残余网络Gf中寻找一条增广路径。算法步骤如下：</p>
<ul>
<li>初始化： 创建流矩阵flow，flow[i][j]均初始化为0</li>
<li>循环迭代：<ul>
<li>根据flow和G创建残余网络Gf，寻找增广路径</li>
<li>若增广路径不存在，则跳出迭代，证明现在的流就是最大流</li>
<li>若增广路径存在，则更新流矩阵。更新方法为：<ul>
<li>取出增广路径的残余容量 cf(p)= min {cf(u,v):(u,v)属于路径p}，然后更新增广路径p中的边(u,v)：<ul>
<li>若(u,v)属于图G的边E，则 flow[u][v]=flow[u][v]+cf(p)</li>
<li>若(v,u)属于图G的边E，则 flow[u][v]=flow[u][v]-cf(p)</li>
</ul>
</li>
</ul>
</li>
</ul>
</li>
<li>返回流矩阵 flow</li>
</ul>
<h3>算法性能</h3>
<p>ford_fulkerson算法运行时间取决于如何寻找增广路径。如果选择不好，算法可能不会终止：流的值会随着后续的递增而增加， 但是它却不一定收敛于最大的流值。如果用广度优先搜索来寻找增广路径，算法的运行时间将会是多项式数量级。</p>
<p>假定最大流问题中的容量均为整数，由于流量值每次迭代中最少增加一个单位，因此算法运行时间为 O(E|f*|) ,|f*|为最大流的值 </p>

<p>Definition at line <a class="el" href="fordfulkerson_8h_source.html#l00178">178</a> of file <a class="el" href="fordfulkerson_8h_source.html">fordfulkerson.h</a>.</p>

</div>
</div>
<a class="anchor" id="ab134ec014d01e25ec2ed7d2c97babe23"></a>
<div class="memitem">
<div class="memproto">
<div class="memtemplate">
template&lt;typename GraphType &gt; </div>
      <table class="memname">
        <tr>
          <td class="memname">std::array&lt;std::array&lt;typename GraphType::EWeightType,GraphType::NUM&gt;,GraphType::NUM&gt; IntroductionToAlgorithm::GraphAlgorithm::generic_push_relabel </td>
          <td>(</td>
          <td class="paramtype">std::shared_ptr&lt; GraphType &gt;&#160;</td>
          <td class="paramname"><em>graph</em>, </td>
        </tr>
        <tr>
          <td class="paramkey"></td>
          <td></td>
          <td class="paramtype">typename GraphType::VIDType&#160;</td>
          <td class="paramname"><em>src</em>, </td>
        </tr>
        <tr>
          <td class="paramkey"></td>
          <td></td>
          <td class="paramtype">typename GraphType::VIDType&#160;</td>
          <td class="paramname"><em>dst</em>&#160;</td>
        </tr>
        <tr>
          <td></td>
          <td>)</td>
          <td></td><td></td>
        </tr>
      </table>
</div><div class="memdoc">

<p>generic_push_relabel：最大流的推送-重贴标签算法。算法导论26章26.4节 </p>
<dl class="params"><dt>Parameters</dt><dd>
  <table class="params">
    <tr><td class="paramname">graph:指定流网络。它必须非空，否则抛出异常</td><td></td></tr>
    <tr><td class="paramname">src</td><td>流的源点，必须有效否则抛出异常 </td></tr>
    <tr><td class="paramname">dst</td><td>流的汇点，必须有效否则抛出异常 </td></tr>
  </table>
  </dd>
</dl>
<dl class="section return"><dt>Returns</dt><dd>: 最大流矩阵</dd></dl>
<p>如果src、dst任何一个顶点无效，则抛出异常：</p>
<ul>
<li>如果指定的顶点<code>id</code>不在<code>[0,N)</code>之间，则无效</li>
<li>如果不存在某个顶点与指定的顶点<code>id</code>相同，则无效</li>
</ul>
<h2>最大流</h2>
<p>流网络G=（V,E）是一个有向图，图中每条边(u,v)属于E都有一个正的容量值c(u,v)&gt;0。而且如果边集合E中包含一条边(u,v)，则图中不存在反向边 (v,u)。为方便起见，假设(u,v)不属于E,定义c(u,v)=0（即无效权重为0），并且在图中不允许自循环。</p>
<p>在流网络中存在两个特殊点：源结点s和汇点t。假定每一个结点都在从源点s到汇点t的某条路径上。即对于每个结点v属于E，存在某条路径 s&ndash;&gt;v&ndash;&gt;t。</p>
<p>G中的流是一个实值函数f:V*V&ndash;&gt;R，满足下面两条性质：</p>
<ul>
<li>容量限制：对于所有结点u,v属于V，要求0&lt;= f(u,v) &lt;= c(u,v)</li>
<li>流量守恒： 对于所有结点u属于V-{s,t}，要求：从u进入的流等于从u出去的流</li>
</ul>
<p>对于(u,v)不属于E的情况，从结点u到v之间没有流，因此f(u,v)=0。我们称非负数值f(u,v)为从结点u到v的流。一个流f的值 |f|=从源点流出的总流量- 流入源结点的总流量</p>
<p>最大流问题：给定流网络G、一个源结点s、一个汇点t,找出值最大的一个流</p>
<h2>generic_push_relabel 算法</h2>
<h3>算法原理</h3>
<p>目前最大流的最快实现是基于推送-重贴标签算法。推送-重贴标签算法比 Ford-fulkserson的局域性更强。它不是对整个残余网络进行检查， 而是一个结点一个结点的查看，每一步只检查当前结点的邻结点。与 Ford-fulkerson 方法不同， 推送-重贴标签算法并不在整个执行过程中保持流量守恒性质，而是维持一个预流，该流是一个 V*V &ndash;&gt; R的函数f,它满足容量限制单不满足流量守恒性质。 进入一个点的流量可以超过流出该结点的流量，我们称结点u的 （进入流量-流出流量）=e(u)为结点u的超额流。 对于结点u属于V-{s,t}，如果 e(u)&gt;0，则称结点u溢出。</p>
<p>考虑一个流网络G=(V,E)，我们将有向边看作管道，连接管道的结点有两个性质：</p>
<ul>
<li>为了容纳额外的流e，每个结点都隐藏有一个外流的管道，该管道通向一个容量无穷大的水库</li>
<li>每个结点都有一个高度h，高度的值随着算法的推进而增加</li>
</ul>
<p>高度h满足下面性质：h(s)=|V|,h(t)=0,对于所有的边(u,v)属于E_f（残余网络中的边），则有 h(u)&lt;=h(v)+1</p>
<p>结点的高度h决定了流的推送方向：我们只从高处向低处push流。我们将源的高度固定在|V|，将汇点的高度固定在0。其他结点的高度初始时为0， 但是随着时间的推移而不断增加。</p>
<p>generic_push_relabel算法首先从源结点往下发送尽可能多的流到汇点，发送的流量为源结点所发出的所有管道的流量之和。 当流进入一个中间结点时，他们被收集在该结点的水库中。</p>
<p>算法过程中，可能发现所有离开结点u的未充满的管道高度都比u大或者和u相等。此时为了消除结点u的超额流量，必须增加结点u的高度。 这就是“重贴标签”操作，我们将结点u的高度增加到比其最低的邻居结点的高度多1个单位的高度，这里要求结点u到该邻居结点的管道必须未充满。 因此在执行重贴标签后，一个结点u至少有一个流出管道。可以通过它推送更多的流。</p>
<p>最终一旦所有水库为空，则预流不但是“合法”的流，也是一个最大流。</p>
<h3>基本操作</h3>
<h4>push 操作</h4>
<p>如果一个结点 u是一个溢出结点，则至少有一条入边，假设为(v,u)，且f(v,u)&gt;0。此时残留网络G_f中的边c_f(u,v)&gt;0。如果此时还有h(u)=h(v)+1， 则可以对边(u,v)执行push操作。</p>
<p>因为结点u有一个正的超额流u.e，且边(u,v)的残余容量为正，因此可以增加结点u到v的流，增加的幅度为min(u.e,c_f(u,v))，这种幅度的增加不会导致 u.e为负值或者容量 c(u,v) 被突破</p>
<p>push操作步骤：</p>
<ul>
<li>计算残余容量 c_f(u,v)</li>
<li>计算流的增加幅度 delt_f=min(u.e,c_f(u,v))</li>
<li>更新流：<ul>
<li>如果 (u,v) 属于 E，则 f(u,v) += delt_f</li>
<li>如果 (v,u) 属于 E，则 f(v,u) -= delt_f</li>
</ul>
</li>
<li>更新溢出流量：<ul>
<li>u.e -= delt(u,v)</li>
<li>v.e += delt(u,v)</li>
</ul>
</li>
</ul>
<h4>relabel 操作</h4>
<p>如果结点u溢出，并且对于所有边(u,v)属于E_f(残留网络G_f中的边)，有u.h&lt;=v.h，则可以对结点u执行relabel操作。 当调用relabel操作时，E_f必须包含至少一条从结点u出发的边。</p>
<p>relabel 步骤：</p>
<ul>
<li>计算 min{v.h:(u,v)属于E_f}</li>
<li>u.h=1+ min{v.h:(u,v)属于E_f}</li>
</ul>
<h3>算法步骤</h3>
<ul>
<li>初始化操作：<ul>
<li>初始化预流 flow: flow(u,v)=c(u,v)如果u=s;否则 flow(u,v)=0</li>
<li>初始化高度函数 h: h(s)=|V|;h(u)=0, u属于 V-{s}</li>
<li>初始化超额流量 e： e(u)=c(s,u)，u为与源s相邻的结点; e(u)=0，u为与源s不相邻的结点; e(s)初始化为所有s出发的管道之后的相反数</li>
</ul>
</li>
<li>执行循环，直到所有结点u属于V-{s,t}不存在超额流量e为止。循环内执行：<ul>
<li>如果可以执行 push 操作，则执行push操作</li>
<li>如果不能执行 push 操作，又由于存在超额流量 e&gt;0 的结点，因此必然可以执行 relabel 操作。则执行 relabel 操作</li>
</ul>
</li>
</ul>
<h3>算法性能</h3>
<p>算法性能：时间复杂度 O(V^2 E) </p>

<p>Definition at line <a class="el" href="genericpushrelabel_8h_source.html#l00373">373</a> of file <a class="el" href="genericpushrelabel_8h_source.html">genericpushrelabel.h</a>.</p>

</div>
</div>
<a class="anchor" id="a1581960f77507024b39572aeb6d1fbd6"></a>
<div class="memitem">
<div class="memproto">
<div class="memtemplate">
template&lt;typename VertexType &gt; </div>
      <table class="memname">
        <tr>
          <td class="memname">std::vector&lt;typename VertexType::VIDType&gt; IntroductionToAlgorithm::GraphAlgorithm::get_path </td>
          <td>(</td>
          <td class="paramtype">const std::shared_ptr&lt; VertexType &gt;&#160;</td>
          <td class="paramname"><em>v_from</em>, </td>
        </tr>
        <tr>
          <td class="paramkey"></td>
          <td></td>
          <td class="paramtype">const std::shared_ptr&lt; VertexType &gt;&#160;</td>
          <td class="paramname"><em>v_to</em>&#160;</td>
        </tr>
        <tr>
          <td></td>
          <td>)</td>
          <td></td><td></td>
        </tr>
      </table>
</div><div class="memdoc">

<p>get_path：获取两个顶点之间的路径 </p>
<dl class="params"><dt>Parameters</dt><dd>
  <table class="params">
    <tr><td class="paramname">v_from</td><td>起始顶点 </td></tr>
    <tr><td class="paramname">v_to</td><td>终止顶点 </td></tr>
  </table>
  </dd>
</dl>
<dl class="section return"><dt>Returns</dt><dd>: 两个顶点之间的路径包含的顶点的<code>id</code>序列</dd></dl>
<p>获取从<code>v_from</code>到<code>v_to</code>之间的一条路径，该路径用途经的顶点的<code>id</code>来表示，是一个<code>std::vector&lt;typename VertexType::VIDType&gt;</code>类型。</p>
<p>要求<code>v_from</code>与<code>v_to</code>非空，否则抛出异常 </p>

<p>Definition at line <a class="el" href="header_8h_source.html#l00141">141</a> of file <a class="el" href="header_8h_source.html">header.h</a>.</p>

</div>
</div>
<a class="anchor" id="a267d39a5bb09200f37a1cd2f0ad4f69f"></a>
<div class="memitem">
<div class="memproto">
<div class="memtemplate">
template&lt;typename GraphType &gt; </div>
      <table class="memname">
        <tr>
          <td class="memname">std::shared_ptr&lt;<a class="el" href="struct_introduction_to_algorithm_1_1_graph_algorithm_1_1_graph.html">Graph</a>&lt;GraphType::NUM+1,typename GraphType::VertexType&gt; &gt; IntroductionToAlgorithm::GraphAlgorithm::graph_plus_1v </td>
          <td>(</td>
          <td class="paramtype">std::shared_ptr&lt; GraphType &gt;&#160;</td>
          <td class="paramname"><em>graph</em></td><td>)</td>
          <td></td>
        </tr>
      </table>
</div><div class="memdoc">

<p>graph_plus_1v：根据图graph生成一个新图。算法导论25章25.2节 </p>
<dl class="params"><dt>Parameters</dt><dd>
  <table class="params">
    <tr><td class="paramname">graph:指定的有向图。它必须非空，否则抛出异常</td><td></td></tr>
  </table>
  </dd>
</dl>
<dl class="section return"><dt>Returns</dt><dd>: 一个新图</dd></dl>
<p>根据图graph生成一个新图new_graph。new_graph的顶点 graph的顶点加上一个新顶点s； new_graph的边为graph的边加上{(s,v):v属于graph的顶点}; new_graph的边的权重为graph的边权重，以及 w(s,v)=0 &gt;注意：设原图有N个顶点，则新图有N+1个顶点</p>
<p>本函数是 johnson 算法的辅助函数 </p>

<p>Definition at line <a class="el" href="johnson_8h_source.html#l00046">46</a> of file <a class="el" href="johnson_8h_source.html">johnson.h</a>.</p>

</div>
</div>
<a class="anchor" id="af1dfc9c1874850fb1415db3644497777"></a>
<div class="memitem">
<div class="memproto">
<div class="memtemplate">
template&lt;typename GraphType &gt; </div>
      <table class="memname">
        <tr>
          <td class="memname">void IntroductionToAlgorithm::GraphAlgorithm::initial_vertex_NList </td>
          <td>(</td>
          <td class="paramtype">std::shared_ptr&lt; GraphType &gt;&#160;</td>
          <td class="paramname"><em>graph</em>, </td>
        </tr>
        <tr>
          <td class="paramkey"></td>
          <td></td>
          <td class="paramtype">typename GraphType::VIDType&#160;</td>
          <td class="paramname"><em>src</em>, </td>
        </tr>
        <tr>
          <td class="paramkey"></td>
          <td></td>
          <td class="paramtype">typename GraphType::VIDType&#160;</td>
          <td class="paramname"><em>dst</em>&#160;</td>
        </tr>
        <tr>
          <td></td>
          <td>)</td>
          <td></td><td></td>
        </tr>
      </table>
</div><div class="memdoc">

<p>initial_vertex_NList：前置重贴标签算法中的初始化邻接链表操作 </p>
<dl class="params"><dt>Parameters</dt><dd>
  <table class="params">
    <tr><td class="paramname">graph:指定流网络。它必须非空，否则抛出异常</td><td></td></tr>
    <tr><td class="paramname">src</td><td>流的源点，必须有效否则抛出异常 </td></tr>
    <tr><td class="paramname">dst</td><td>流的汇点，必须有效否则抛出异常 </td></tr>
  </table>
  </dd>
</dl>
<dl class="section return"><dt>Returns</dt><dd>: void</dd></dl>
<p>如果src、dst任何一个顶点无效，则抛出异常：</p>
<ul>
<li>如果指定的顶点<code>id</code>不在<code>[0,N)</code>之间，则无效</li>
<li>如果不存在某个顶点与指定的顶点<code>id</code>相同，则无效</li>
</ul>
<p>该操作将初始化除了s、t之外所有顶点的邻接链表 </p>

<p>Definition at line <a class="el" href="relabeltofront_8h_source.html#l00153">153</a> of file <a class="el" href="relabeltofront_8h_source.html">relabeltofront.h</a>.</p>

</div>
</div>
<a class="anchor" id="aeaf3e258f5ae9aed76158255fa603c00"></a>
<div class="memitem">
<div class="memproto">
<div class="memtemplate">
template&lt;typename GraphType &gt; </div>
      <table class="memname">
        <tr>
          <td class="memname">void IntroductionToAlgorithm::GraphAlgorithm::initialize_preflow </td>
          <td>(</td>
          <td class="paramtype">std::shared_ptr&lt; GraphType &gt;&#160;</td>
          <td class="paramname"><em>graph</em>, </td>
        </tr>
        <tr>
          <td class="paramkey"></td>
          <td></td>
          <td class="paramtype">typename GraphType::VIDType&#160;</td>
          <td class="paramname"><em>src</em>, </td>
        </tr>
        <tr>
          <td class="paramkey"></td>
          <td></td>
          <td class="paramtype">std::array&lt; std::array&lt; typename GraphType::EWeightType, GraphType::NUM &gt;, GraphType::NUM &gt; &amp;&#160;</td>
          <td class="paramname"><em>flow</em>&#160;</td>
        </tr>
        <tr>
          <td></td>
          <td>)</td>
          <td></td><td></td>
        </tr>
      </table>
</div><div class="memdoc">

<p>initialize_preflow：generic_push_relabel算法的初始化操作。算法导论26章26.4节 </p>
<dl class="params"><dt>Parameters</dt><dd>
  <table class="params">
    <tr><td class="paramname">graph:指定流网络。它必须非空，否则抛出异常</td><td></td></tr>
    <tr><td class="paramname">src</td><td>流的源点，必须有效否则抛出异常 </td></tr>
    <tr><td class="paramname">flow</td><td>预流的引用（执行过程中会更新预流） </td></tr>
  </table>
  </dd>
</dl>
<dl class="section return"><dt>Returns</dt><dd>: void</dd></dl>
<p>如果src无效，则抛出异常：</p>
<ul>
<li>如果指定的顶点<code>id</code>不在<code>[0,N)</code>之间，则无效</li>
<li>如果不存在某个顶点与指定的顶点<code>id</code>相同，则无效</li>
</ul>
<p>初始化操作执行下列操作：</p>
<ul>
<li>初始化预流 flow: flow(u,v)=c(u,v)如果u=s;否则 flow(u,v)=0</li>
<li>初始化高度函数 h: h(s)=|V|;h(u)=0, u属于 V-{s}</li>
<li>初始化超额流量 e： e(u)=c(s,u)，u为与源s相邻的结点; e(u)=0，u为与源s不相邻的结点; e(s)初始化为所有s出发的管道之后的相反数 <blockquote class="doxtable">
<p>由顶点的<code>key</code>属性存储超额流量e</p>
</blockquote>
</li>
</ul>

<p>Definition at line <a class="el" href="genericpushrelabel_8h_source.html#l00227">227</a> of file <a class="el" href="genericpushrelabel_8h_source.html">genericpushrelabel.h</a>.</p>

</div>
</div>
<a class="anchor" id="a5ed496e8825564d0f9fcfe3b0ac41dec"></a>
<div class="memitem">
<div class="memproto">
<div class="memtemplate">
template&lt;typename GraphType &gt; </div>
      <table class="memname">
        <tr>
          <td class="memname">void IntroductionToAlgorithm::GraphAlgorithm::initialize_single_source </td>
          <td>(</td>
          <td class="paramtype">std::shared_ptr&lt; GraphType &gt;&#160;</td>
          <td class="paramname"><em>graph</em>, </td>
        </tr>
        <tr>
          <td class="paramkey"></td>
          <td></td>
          <td class="paramtype">typename GraphType::VIDType&#160;</td>
          <td class="paramname"><em>source_id</em>&#160;</td>
        </tr>
        <tr>
          <td></td>
          <td>)</td>
          <td></td><td></td>
        </tr>
      </table>
</div><div class="memdoc">

<p>initialize_single_source：单源最短路径的初始化操作，算法导论24章24.1节 </p>
<dl class="params"><dt>Parameters</dt><dd>
  <table class="params">
    <tr><td class="paramname">graph:指向图的强指针，必须非空。若为空则抛出异常</td><td></td></tr>
    <tr><td class="paramname">source_id：最小生成树的根结点&lt;tt&gt;id&lt;/tt&gt;，必须有效。若无效则抛出异常</td><td></td></tr>
  </table>
  </dd>
</dl>
<dl class="section return"><dt>Returns</dt><dd>: void</dd></dl>
<p><code>source_id</code>在以下情况下无效：</p>
<ul>
<li><code>source_id</code>不在区间<code>[0,N)</code>之间时，<code>source_id</code>无效</li>
<li><code>graph</code>中不存在某个顶点的<code>id</code>等于<code>source_id</code>时，<code>source_id</code>无效</li>
</ul>
<p>单源最短路径的初始化操作将所有的结点的<code>key</code>设置为正无穷，将所有结点的<code>parent</code>设为空。然后将源结点的<code>key</code>设为0。</p>
<p>性能：时间复杂度O(V) </p>

<p>Definition at line <a class="el" href="bellmanford_8h_source.html#l00043">43</a> of file <a class="el" href="bellmanford_8h_source.html">bellmanford.h</a>.</p>

</div>
</div>
<a class="anchor" id="a4f664c13605fc87ca8d26f4aad5a9fa2"></a>
<div class="memitem">
<div class="memproto">
<div class="memtemplate">
template&lt;typename T &gt; </div>
      <table class="memname">
        <tr>
          <td class="memname">bool IntroductionToAlgorithm::GraphAlgorithm::is_unlimit </td>
          <td>(</td>
          <td class="paramtype">T&#160;</td>
          <td class="paramname"><em>t</em></td><td>)</td>
          <td></td>
        </tr>
      </table>
</div><div class="memdoc">

<p>is_unlimit：判断是否正无穷 </p>
<dl class="params"><dt>Parameters</dt><dd>
  <table class="params">
    <tr><td class="paramname">t</td><td>待判断的数 </td></tr>
  </table>
  </dd>
</dl>
<dl class="section return"><dt>Returns</dt><dd>: 如果该数是正无穷大，则返回<code>true</code>，否则返回<code>false</code></dd></dl>
<p>将本函数判断一个数是否正无穷；若是则返回true;若不是则返回false</p>
<p>这里将大于等于<code>std::numeric_limits&lt;T&gt;::max()/3</code>的数判断结果为正无穷 &gt;因为考虑到正无穷减去一个数必须保证结果也是正无穷 </p>

<p>Definition at line <a class="el" href="header_8h_source.html#l00126">126</a> of file <a class="el" href="header_8h_source.html">header.h</a>.</p>

</div>
</div>
<a class="anchor" id="a856b132d068d0553355203a16cdec97d"></a>
<div class="memitem">
<div class="memproto">
<div class="memtemplate">
template&lt;typename GraphType &gt; </div>
      <table class="memname">
        <tr>
          <td class="memname">std::array&lt;std::array&lt;typename GraphType::EWeightType ,GraphType::NUM&gt;,GraphType::NUM&gt; IntroductionToAlgorithm::GraphAlgorithm::johnson </td>
          <td>(</td>
          <td class="paramtype">std::shared_ptr&lt; GraphType &gt;&#160;</td>
          <td class="paramname"><em>graph</em></td><td>)</td>
          <td></td>
        </tr>
      </table>
</div><div class="memdoc">

<p>johnson：返回所有节点对的最短路径的johnson算法。算法导论25章25.3节 </p>
<dl class="params"><dt>Parameters</dt><dd>
  <table class="params">
    <tr><td class="paramname">graph:指定的有向图。它必须非空，否则抛出异常</td><td></td></tr>
  </table>
  </dd>
</dl>
<dl class="section return"><dt>Returns</dt><dd>: 一个n*n的矩阵(d_i_j)，其中 d_i_j 代表的是结点i到j的一条最短路径的权重</dd></dl>
<h2>所有结点对的最短路径</h2>
<p>给定一个带权重的有向图G=(V,E)，其权重函数为w:E-&gt;R，该函数将边映射到实值权重上。我们希望找到对于所有的结点对u,v属于V，找出一条从结点u 到结点v的最短路径，以及这条路径的权重。</p>
<p>与单源最短路径不同中使用邻接表来表示图不同，本章的多数算法使用邻接矩阵来表示图。该矩阵代表的是一个有n个结点的有向图G=(V,E)的边的权重W=(w_i_j)， 其中 w_i_j =:</p>
<ul>
<li>0:若i=j</li>
<li>有向边(i,j)的权重，若i!=j且(i,j)属于E</li>
<li>正无穷，若 i!=j且(i,j)不属于E</li>
</ul>
<p>我们允许存在负权重的边，目前仍然假定图中不存在权重为负值的环路。</p>
<p>本章讨论的所有结点对最短路径的算法的输出也是一个n*n的矩阵D=(d_i_j)，其中 d_i_j 代表的是结点i到j的一条最短路径的权重。</p>
<p>有时候为了解决所有结点对最短路径问题，我们不仅要计算出最短路径权重，还需要计算出前驱结点矩阵 II=(pai_i_j)，其中 pai_i_j在i=j或者从i到j 不存在路径时为NIL，在其他情况下给出的是从结点i到结点j的某条最短路径上结点j的前驱结点。由矩阵II的第i行所诱导的子图应当是一棵根节点为i 的最短路径树。</p>
<h2>Johnson算法</h2>
<h3>算法原理</h3>
<p>对于稀疏图来说Johnson算法的渐近表现要优于重复平方法和Floyd-Warshall算法。Johnson算法要么返回一个包含所有结点对的最短路径权重的矩阵， 要么报告输入图中包含一个权重为负值的环路。Johnson算法在运行中需要使用Dijkstra算法和Bellman-Ford算法作为自己的子程序。</p>
<p>Johnson算法使用一种称为重赋权重的技术。若图G=(V,E)中所有边权重w都为非负值，则可以通过对每一对顶点运行一次Dijkstra 算法来找到所有顶点对直接的最短路径。如果图G包含负权重的边，但没有权重为负值的环路，则需要计算出一组新的非负权重值，然后用同样的方法。 新赋的权重w'要求满足一下性质：</p>
<ul>
<li>对于所有结点对u,v属于V，一条路径p实在使用权重函数w时从u到v的一条最短路径，当且仅当p实在使用权重函数w' 时从u到v的一条最短路径</li>
<li>对于所有的边(u,v)，新权重w'(u,v)非负</li>
</ul>
<p>对于给定的有向图G=(V,E)，权重函数w：E-&gt;R 。我们制作一副新图G'=(V',E')，其中V'=V并上{s}，s是一个新结点，s不属于V。 E'=E并上{(s,v);v属于V}。我们对权重函数w进行扩展，使得对于所有结点v属于V，有w(s,v)=0。 对所有的结点v属于V'，我们定义h(v)=delt(s,v)。定义w'(u,v)=w(u,v)+h(u)-h(v)</p>
<h3>算法步骤</h3>
<ul>
<li>重赋权重：<ul>
<li>创建新图 new_graph</li>
<li>对新图执行 bellman_ford 的调用，源点为新创建的结点s</li>
<li>如果有负权值的环路，则抛出异常。</li>
<li>如果没有负权重环路，则创建h函数，并对new_graph中的所有边执行重新赋权</li>
</ul>
</li>
<li>在 new_graph上，除了新的顶点s之外的所有顶点v,以v为源顶点执行dijkstra过程。D[i][j]等于 new_graph 中以i为源点到j的最短路径的权重的修正值， 修正的方法就是重新赋权的逆过程。</li>
<li>返回矩阵 D</li>
</ul>
<h3>算法性能</h3>
<p>时间复杂度 O（V^2 lgV + VE) </p>

<p>Definition at line <a class="el" href="johnson_8h_source.html#l00139">139</a> of file <a class="el" href="johnson_8h_source.html">johnson.h</a>.</p>

</div>
</div>
<a class="anchor" id="a2575c09c42d0b30b57702c9379d2fbfb"></a>
<div class="memitem">
<div class="memproto">
<div class="memtemplate">
template&lt;typename GraphType , typename ActionType  = std::function&lt; void(typename GraphType::VIDType,typename GraphType::VIDType)&gt;&gt; </div>
      <table class="memname">
        <tr>
          <td class="memname">GraphType::EWeightType IntroductionToAlgorithm::GraphAlgorithm::kruskal </td>
          <td>(</td>
          <td class="paramtype">std::shared_ptr&lt; GraphType &gt;&#160;</td>
          <td class="paramname"><em>graph</em>, </td>
        </tr>
        <tr>
          <td class="paramkey"></td>
          <td></td>
          <td class="paramtype">ActionType&#160;</td>
          <td class="paramname"><em>pre_action</em> = <code>[](typename&#160;GraphType::VIDType,typename&#160;GraphType::VIDType){}</code>, </td>
        </tr>
        <tr>
          <td class="paramkey"></td>
          <td></td>
          <td class="paramtype">ActionType&#160;</td>
          <td class="paramname"><em>post_action</em> = <code>[](typename&#160;GraphType::VIDType,typename&#160;GraphType::VIDType){}</code>&#160;</td>
        </tr>
        <tr>
          <td></td>
          <td>)</td>
          <td></td><td></td>
        </tr>
      </table>
</div><div class="memdoc">

<p>kruskal：最小生成树的Kruskal算法，算法导论23章23.2节 </p>
<dl class="params"><dt>Parameters</dt><dd>
  <table class="params">
    <tr><td class="paramname">graph:指向图的强指针，必须非空。若为空则抛出异常</td><td></td></tr>
    <tr><td class="paramname">source_id：最小生成树的根结点&lt;tt&gt;id&lt;/tt&gt;，必须有效。若无效则抛出异常</td><td></td></tr>
    <tr><td class="paramname">pre_action:一个可调用对象，在每次从最小优先级队列中弹出最小顶点时立即调用，调用参数为该顶点的&lt;tt&gt;id&lt;/tt&gt;。默认为空操作，即不进行任何操作</td><td></td></tr>
    <tr><td class="paramname">post_action:一个可调用对象，在每次从最小优先级队列中弹出最小顶点并处理完它的边时立即调用，调用参数为该顶点的&lt;tt&gt;id&lt;/tt&gt;。默认为空操作，即不进行任何操作</td><td></td></tr>
  </table>
  </dd>
</dl>
<dl class="section return"><dt>Returns</dt><dd>: 最小生成树的权重</dd></dl>
<h2>最小生成树</h2>
<p>最小生成树：对于一个连通无向图G=(V,E)，对于每一条边(u,v)属于E都赋予了一个权重w(u,v)。我们希望找出一个无环子集T，其中T为E的子集，使得所有的顶点V位于T中， 同时T具有最小的权重。由于T是无环的，且连通所有结点因此T必然是一棵树。我们称这样的树为生成树。称从G中求取该生成树的问题为最小生成树问题。</p>
<p>通用的最小生成树使用贪心策略。该策略在每个时刻找到最小生成树的一条边，并在整个策略过程中维持循环不变式：边的集合A在每次循环之前是某棵最小生成树的一个子集。</p>
<p>在每一步，选择一条边(u,v)，将其加入集合A中，使得A不违反循环不变式。称这样的边(u,v)为边集合A的安全边。</p>
<h2>Kruskal 算法</h2>
<h3>算法原理</h3>
<p>在Kruskal算法中集合A是一个森林，其结点就是G的结点。Kruskal算法找到安全边的办法是：在所有连接森林中两棵不同树的边里面，找到权重最小的边(u,v)。 Kruskal算法使用一个不相交集合数据结构来维护几个互不相交的元素集合。每个集合代表当前森林中的一棵树</p>
<h3>算法步骤</h3>
<ul>
<li>初始化：将集合A置为空；对G中的每一个结点v,以它为根构造一棵单根树</li>
<li>将G中的边E按照权重单调递增的顺序排序</li>
<li>循环挑选E中的(u,v)，按照单调增的顺序。在循环内执行：<ul>
<li>如果u所在的树不等于v所在的树，则将(u,v)加入A中，并且合并u所在的树与v所在的树</li>
</ul>
</li>
</ul>
<p>&gt;根据算法的特征，如果图中只有一个顶点，算法得到的集合A为空集；但是实际上集合A应该包含该顶点。这是算法在极端情况下的BUG。</p>
<h3>算法性能</h3>
<p>Kruskal算法运行时间依赖于不相交集合数据结构的实现方式。如果采用算法导论21.3节讨论的不相交集合森林实现（也是我在src/set_algorithms/disjoint_set中实现的）， 则Kruskal算法的时间为 O(ElgV) </p>

<p>Definition at line <a class="el" href="kruskal_8h_source.html#l00069">69</a> of file <a class="el" href="kruskal_8h_source.html">kruskal.h</a>.</p>

</div>
</div>
<a class="anchor" id="ab9dcca59a42c708c137571d194c45bd9"></a>
<div class="memitem">
<div class="memproto">
<div class="memtemplate">
template&lt;typename GraphType &gt; </div>
      <table class="memname">
        <tr>
          <td class="memname">std::array&lt;std::array&lt;typename GraphType::EWeightType ,GraphType::NUM&gt;,GraphType::NUM&gt; IntroductionToAlgorithm::GraphAlgorithm::matrix_shortest_path </td>
          <td>(</td>
          <td class="paramtype">std::shared_ptr&lt; GraphType &gt;&#160;</td>
          <td class="paramname"><em>graph</em></td><td>)</td>
          <td></td>
        </tr>
      </table>
</div><div class="memdoc">

<p>matrix_shortest_path：返回所有节点对的最短路径的矩阵乘法算法。算法导论25章25.1节 </p>
<dl class="params"><dt>Parameters</dt><dd>
  <table class="params">
    <tr><td class="paramname">graph:指定的有向图。它必须非空，否则抛出异常</td><td></td></tr>
  </table>
  </dd>
</dl>
<dl class="section return"><dt>Returns</dt><dd>: 一个n*n的矩阵(d_i_j)，其中 d_i_j 代表的是结点i到j的一条最短路径的权重</dd></dl>
<h2>所有结点对的最短路径</h2>
<p>给定一个带权重的有向图G=(V,E)，其权重函数为w:E-&gt;R，该函数将边映射到实值权重上。我们希望找到对于所有的结点对u,v属于V，找出一条从结点u 到结点v的最短路径，以及这条路径的权重。</p>
<p>与单源最短路径不同中使用邻接表来表示图不同，本章的多数算法使用邻接矩阵来表示图。该矩阵代表的是一个有n个结点的有向图G=(V,E)的边的权重W=(w_i_j)， 其中 w_i_j =:</p>
<ul>
<li>0:若i=j</li>
<li>有向边(i,j)的权重，若i!=j且(i,j)属于E</li>
<li>正无穷，若 i!=j且(i,j)不属于E</li>
</ul>
<p>我们允许存在负权重的边，目前仍然假定图中不存在权重为负值的环路。</p>
<p>本章讨论的所有结点对最短路径的算法的输出也是一个n*n的矩阵D=(d_i_j)，其中 d_i_j 代表的是结点i到j的一条最短路径的权重。</p>
<p>有时候为了解决所有结点对最短路径问题，我们不仅要计算出最短路径权重，还需要计算出前驱结点矩阵 II=(pai_i_j)，其中 pai_i_j在i=j或者从i到j 不存在路径时为NIL，在其他情况下给出的是从结点i到结点j的某条最短路径上结点j的前驱结点。由矩阵II的第i行所诱导的子图应当是一棵根节点为i 的最短路径树。</p>
<h2>matrix_shortest_path 算法</h2>
<h3>算法原理</h3>
<p>matrix_shortest_path采用动态规划算法求解。考虑从结点i到j的一条最短路径p，假定p最多包含m条边，假定没有权重为负值的环路，且m为有限值。 如果 i=j，则p的权重为0且不包含任何边；如果i和j不同，则将路径p分解为 i&ndash;&gt;k(经过路径p')&ndash;&gt;j，其中路径p'最多包含m-1条边。</p>
<p>定义 l_i_j&lt;m&gt;为从结点i到j的最多包含m条边的任意路径中的最小权重，则有：l_i_j&lt;m&gt;=</p>
<ul>
<li>0：如果i=j</li>
<li>正无穷:如果 i!=j</li>
</ul>
<p>对于m&gt;=1，我们有： l_i_j&lt;m&gt;=min(l_i_j&lt;m-1&gt;，min_(1&lt;=k&lt;=n){l_i_k&lt;m-1&gt;+w_k_j})=min_(1&lt;=k&lt;=n){l_i_k&lt;m-1&gt;+w_k_j}。 如果图G不包含负值的环路，则对于每一对结点i,j，如果他们delt(i,j)&lt;正无穷，则从i到j之间存在一条最短路径。由于该路径是简单路径， 则包含的边最多为n-1条。因此delt(i,j)=l_i_j&lt;n-1&gt;=l_i_j&lt;n&gt;=...</p>
<p>matrix_shortest_path算法根据输入矩阵W=(w_i_j)，计算出矩阵序列 L&lt;1&gt;，L&lt;2&gt;,...L&lt;n-1&gt;。最后的矩阵L&lt;n-1&gt;包含的是最短路径的权重。 其中L&lt;1&gt;=W。算法的核心是extend_path函数，它将最近计算出的路径扩展了一条边</p>
<h3>算法步骤</h3>
<ul>
<li>初始化：从图中获取权重矩阵 W</li>
<li>执行循环扩展L，其中 L&lt;0&gt;=W, L&lt;k&gt;=extend_path(L&lt;k-1&gt;,W)</li>
<li>最终返回 L&lt;N-1&gt;</li>
</ul>
<h3>算法性能</h3>
<p>时间复杂度O(V^4) </p>

<p>Definition at line <a class="el" href="matrix__shortest__path_8h_source.html#l00129">129</a> of file <a class="el" href="matrix__shortest__path_8h_source.html">matrix_shortest_path.h</a>.</p>

</div>
</div>
<a class="anchor" id="a6eb979447eeb937df4158f9646e20dde"></a>
<div class="memitem">
<div class="memproto">
<div class="memtemplate">
template&lt;typename GraphType &gt; </div>
      <table class="memname">
        <tr>
          <td class="memname">std::array&lt;std::array&lt;typename GraphType::EWeightType ,GraphType::NUM&gt;,GraphType::NUM&gt; IntroductionToAlgorithm::GraphAlgorithm::matrix_shortest_path_fast </td>
          <td>(</td>
          <td class="paramtype">std::shared_ptr&lt; GraphType &gt;&#160;</td>
          <td class="paramname"><em>graph</em></td><td>)</td>
          <td></td>
        </tr>
      </table>
</div><div class="memdoc">

<p>matrix_shortest_path：返回所有节点对的最短路径的矩阵乘法复平方算法。算法导论25章25.1节 </p>
<dl class="params"><dt>Parameters</dt><dd>
  <table class="params">
    <tr><td class="paramname">graph:指定的有向图。它必须非空，否则抛出异常</td><td></td></tr>
  </table>
  </dd>
</dl>
<dl class="section return"><dt>Returns</dt><dd>: 一个n*n的矩阵(d_i_j)，其中 d_i_j 代表的是结点i到j的一条最短路径的权重</dd></dl>
<h2>所有结点对的最短路径</h2>
<p>给定一个带权重的有向图G=(V,E)，其权重函数为w:E-&gt;R，该函数将边映射到实值权重上。我们希望找到对于所有的结点对u,v属于V，找出一条从结点u 到结点v的最短路径，以及这条路径的权重。</p>
<p>与单源最短路径不同中使用邻接表来表示图不同，本章的多数算法使用邻接矩阵来表示图。该矩阵代表的是一个有n个结点的有向图G=(V,E)的边的权重W=(w_i_j)， 其中 w_i_j =:</p>
<ul>
<li>0:若i=j</li>
<li>有向边(i,j)的权重，若i!=j且(i,j)属于E</li>
<li>正无穷，若 i!=j且(i,j)不属于E</li>
</ul>
<p>我们允许存在负权重的边，目前仍然假定图中不存在权重为负值的环路。</p>
<p>本章讨论的所有结点对最短路径的算法的输出也是一个n*n的矩阵D=(d_i_j)，其中 d_i_j 代表的是结点i到j的一条最短路径的权重。</p>
<p>有时候为了解决所有结点对最短路径问题，我们不仅要计算出最短路径权重，还需要计算出前驱结点矩阵 II=(pai_i_j)，其中 pai_i_j在i=j或者从i到j 不存在路径时为NIL，在其他情况下给出的是从结点i到结点j的某条最短路径上结点j的前驱结点。由矩阵II的第i行所诱导的子图应当是一棵根节点为i 的最短路径树。</p>
<h2>matrix_shortest_path_fast 算法</h2>
<h3>算法原理</h3>
<p>matrix_shortest_path_fast改进了算法matrix_shortest_path。因为我们的目标并不是计算所有的L&lt;m&gt;矩阵，我们感兴趣的仅仅是矩阵L&lt;n-1&gt;。 由matrix_shortest_path过程定义的矩阵乘法是相关的，因此可以仅用t个矩阵乘积来计算矩阵L&lt;n-1&gt;，其中 n为大于lg(n-1)的最小整数。 因此可以用复平方技术来计算上述矩阵序列：</p>
<ul>
<li>L&lt;1&gt;=W</li>
<li>L&lt;2&gt;=W^2=W.W</li>
<li>L&lt;4&gt;=W^4=W^2.W^2</li>
<li>L&lt;8&gt;=W^8=W^4.W^4 ....</li>
</ul>
<h3>算法步骤</h3>
<ul>
<li>初始化：从图中获取权重矩阵 W</li>
<li>执行循环扩展L，其中 L&lt;0&gt;=W, L&lt;2*k&gt;=extend_path(L&lt;k&gt;,L&lt;k&gt;)</li>
<li>最终返回 L&lt;log(N-1)的上界整数&gt;</li>
</ul>
<h3>算法性能</h3>
<p>时间复杂度O(V^3lgV) </p>

<p>Definition at line <a class="el" href="matrix__shortest__path_8h_source.html#l00211">211</a> of file <a class="el" href="matrix__shortest__path_8h_source.html">matrix_shortest_path.h</a>.</p>

</div>
</div>
<a class="anchor" id="a97d248a07f1b31df52be3de3b5570237"></a>
<div class="memitem">
<div class="memproto">
<div class="memtemplate">
template&lt;typename MatrixType &gt; </div>
      <table class="memname">
        <tr>
          <td class="memname">std::string IntroductionToAlgorithm::GraphAlgorithm::matrix_string </td>
          <td>(</td>
          <td class="paramtype">const MatrixType &amp;&#160;</td>
          <td class="paramname"><em>matrix</em></td><td>)</td>
          <td></td>
        </tr>
      </table>
</div><div class="memdoc">

<p>matrix_string：获取矩阵的字符串描述 </p>
<dl class="params"><dt>Parameters</dt><dd>
  <table class="params">
    <tr><td class="paramname">matrix</td><td>矩阵 </td></tr>
  </table>
  </dd>
</dl>
<dl class="section return"><dt>Returns</dt><dd>: 矩阵的字符串描述</dd></dl>
<p>获取矩阵<code>matrix</code>的字符串描述。 </p>

<p>Definition at line <a class="el" href="header_8h_source.html#l00169">169</a> of file <a class="el" href="header_8h_source.html">header.h</a>.</p>

</div>
</div>
<a class="anchor" id="a27dfe859312abba6639bca7b232d4bd6"></a>
<div class="memitem">
<div class="memproto">
<div class="memtemplate">
template&lt;typename GraphType &gt; </div>
      <table class="memname">
        <tr>
          <td class="memname">GraphType::VIDType IntroductionToAlgorithm::GraphAlgorithm::min_v_at_Ef </td>
          <td>(</td>
          <td class="paramtype">std::shared_ptr&lt; GraphType &gt;&#160;</td>
          <td class="paramname"><em>graph</em>, </td>
        </tr>
        <tr>
          <td class="paramkey"></td>
          <td></td>
          <td class="paramtype">typename GraphType::VIDType&#160;</td>
          <td class="paramname"><em>u_id</em>, </td>
        </tr>
        <tr>
          <td class="paramkey"></td>
          <td></td>
          <td class="paramtype">const std::array&lt; std::array&lt; typename GraphType::EWeightType, GraphType::NUM &gt;, GraphType::NUM &gt; &amp;&#160;</td>
          <td class="paramname"><em>flow</em>&#160;</td>
        </tr>
        <tr>
          <td></td>
          <td>)</td>
          <td></td><td></td>
        </tr>
      </table>
</div><div class="memdoc">

<p>min_v_at_Ef：relabel操作中的min_v_at_Ef操作。算法导论26章26.4节 </p>
<dl class="params"><dt>Parameters</dt><dd>
  <table class="params">
    <tr><td class="paramname">graph:指定流网络。它必须非空，否则抛出异常</td><td></td></tr>
    <tr><td class="paramname">u_id</td><td>结点u的id，必须有效否则抛出异常 </td></tr>
    <tr><td class="paramname">flow</td><td>预流 </td></tr>
  </table>
  </dd>
</dl>
<dl class="section return"><dt>Returns</dt><dd>: 所有边(u,v)属于E_f(残留网络G_f中的边)中，高度最小的结点v</dd></dl>
<p>该方法扫描Ef中所有从u出发的边(u,v)，找出高度最小的结点v </p>

<p>Definition at line <a class="el" href="genericpushrelabel_8h_source.html#l00124">124</a> of file <a class="el" href="genericpushrelabel_8h_source.html">genericpushrelabel.h</a>.</p>

</div>
</div>
<a class="anchor" id="aba1581358d79ba82dc4fd0c15bc987e6"></a>
<div class="memitem">
<div class="memproto">
<div class="memtemplate">
template&lt;typename GraphType , typename ActionType  = std::function&lt; void(typename GraphType::VIDType)&gt;&gt; </div>
      <table class="memname">
        <tr>
          <td class="memname">GraphType::EWeightType IntroductionToAlgorithm::GraphAlgorithm::prim </td>
          <td>(</td>
          <td class="paramtype">std::shared_ptr&lt; GraphType &gt;&#160;</td>
          <td class="paramname"><em>graph</em>, </td>
        </tr>
        <tr>
          <td class="paramkey"></td>
          <td></td>
          <td class="paramtype">typename GraphType::VIDType&#160;</td>
          <td class="paramname"><em>source_id</em>, </td>
        </tr>
        <tr>
          <td class="paramkey"></td>
          <td></td>
          <td class="paramtype">ActionType&#160;</td>
          <td class="paramname"><em>pre_action</em> = <code>[](typename&#160;GraphType::VIDType){}</code>, </td>
        </tr>
        <tr>
          <td class="paramkey"></td>
          <td></td>
          <td class="paramtype">ActionType&#160;</td>
          <td class="paramname"><em>post_action</em> = <code>[](typename&#160;GraphType::VIDType){}</code>&#160;</td>
        </tr>
        <tr>
          <td></td>
          <td>)</td>
          <td></td><td></td>
        </tr>
      </table>
</div><div class="memdoc">

<p>prim：最小生成树的Prim算法，算法导论23章23.2节 </p>
<dl class="params"><dt>Parameters</dt><dd>
  <table class="params">
    <tr><td class="paramname">graph:指向图的强指针，必须非空。若为空则抛出异常</td><td></td></tr>
    <tr><td class="paramname">source_id：最小生成树的根结点&lt;tt&gt;id&lt;/tt&gt;，必须有效。若无效则抛出异常</td><td></td></tr>
    <tr><td class="paramname">pre_action:一个可调用对象，在每次从最小优先级队列中弹出最小顶点时立即调用，调用参数为该顶点的&lt;tt&gt;id&lt;/tt&gt;。默认为空操作，即不进行任何操作</td><td></td></tr>
    <tr><td class="paramname">post_action:一个可调用对象，在每次从最小优先级队列中弹出最小顶点并处理完它的边时立即调用，调用参数为该顶点的&lt;tt&gt;id&lt;/tt&gt;。默认为空操作，即不进行任何操作</td><td></td></tr>
  </table>
  </dd>
</dl>
<dl class="section return"><dt>Returns</dt><dd>: 最小生成树的权重</dd></dl>
<p><code>source_id</code>在以下情况下无效：</p>
<ul>
<li><code>source_id</code>不在区间<code>[0,N)</code>之间时，<code>source_id</code>无效</li>
<li><code>graph</code>中不存在某个顶点的<code>id</code>等于<code>source_id</code>时，<code>source_id</code>无效</li>
</ul>
<h2>最小生成树</h2>
<p>最小生成树：对于一个连通无向图G=(V,E)，对于每一条边(u,v)属于E都赋予了一个权重w(u,v)。我们希望找出一个无环子集T，其中T为E的子集，使得所有的顶点V位于T中， 同时T具有最小的权重。由于T是无环的，且连通所有结点因此T必然是一棵树。我们称这样的树为生成树。称从G中求取该生成树的问题为最小生成树问题。</p>
<p>通用的最小生成树使用贪心策略。该策略在每个时刻找到最小生成树的一条边，并在整个策略过程中维持循环不变式：边的集合A在每次循环之前是某棵最小生成树的一个子集。</p>
<p>在每一步，选择一条边(u,v)，将其加入集合A中，使得A不违反循环不变式。称这样的边(u,v)为边集合A的安全边。</p>
<h2>Prim算法</h2>
<h3>算法原理</h3>
<p>在Prim算法所具有的一个性质是集合A中的边总是构成一棵树。这棵树从一个任意的根结点r开始，一直长大到覆盖V中的所有结点为止。算法每一步在连接集合A和A之外的结点的所有边中， 选择一条边加入到A中（经特殊选择的边）。</p>
<p>为了有效地实现Prim算法，需要一种快速的方法来选择一条新的边以便加入到由集合A中的边所构成的树中。在算法执行过程中，所有不在树A中的结点都存放在一个基于key的属性的最小优先级队列Q中。 对于每个结点v，属性v.key保存的是连接v和树中结点的所有边中最小边的权重。若这样的边不存在则权重为正无穷。属性v.pai给出的是结点v在树中的父结点。</p>
<h3>算法步骤</h3>
<ul>
<li>初始化：将所有结点的key设为正无穷，所有结点的父结点置为空(结点构造时，父结点默认为空）</li>
<li>设置源点：将源点的key设为0，</li>
<li>构造最小优先级队列：将所有顶点放入最小优先级队列Q中</li>
<li>循环，直到最小优先级队列为空。循环中执行下列操作：<ul>
<li>弹出最小优先级队列的头部顶点u</li>
<li>从结点u出发的所有边，找出它的另一端的结点v。如果v也在Q中，且w(u,v)&lt;v.key，则证明(u,v)是v到集合A的最短边，因此设置v.pai=u,v.key=w(u,v) &gt;这里隐含着一个最小优先级队列的decreate_key操作</li>
</ul>
</li>
</ul>
<h3>算法性能</h3>
<p>Prim总时间代价为O(VlgV+ElgV)=O(ElgV)(使用最小堆实现的最小优先级队列），或者O(E+VlgV)（使用斐波那契堆实现最小优先级队列） </p>

<p>Definition at line <a class="el" href="prim_8h_source.html#l00077">77</a> of file <a class="el" href="prim_8h_source.html">prim.h</a>.</p>

</div>
</div>
<a class="anchor" id="abd520b7e33d8c1e72b05210d784ac258"></a>
<div class="memitem">
<div class="memproto">
<div class="memtemplate">
template&lt;typename GraphType &gt; </div>
      <table class="memname">
        <tr>
          <td class="memname">void IntroductionToAlgorithm::GraphAlgorithm::push </td>
          <td>(</td>
          <td class="paramtype">std::shared_ptr&lt; GraphType &gt;&#160;</td>
          <td class="paramname"><em>graph</em>, </td>
        </tr>
        <tr>
          <td class="paramkey"></td>
          <td></td>
          <td class="paramtype">typename GraphType::VIDType&#160;</td>
          <td class="paramname"><em>u_id</em>, </td>
        </tr>
        <tr>
          <td class="paramkey"></td>
          <td></td>
          <td class="paramtype">typename GraphType::VIDType&#160;</td>
          <td class="paramname"><em>v_id</em>, </td>
        </tr>
        <tr>
          <td class="paramkey"></td>
          <td></td>
          <td class="paramtype">std::array&lt; std::array&lt; typename GraphType::EWeightType, GraphType::NUM &gt;, GraphType::NUM &gt; &amp;&#160;</td>
          <td class="paramname"><em>flow</em>&#160;</td>
        </tr>
        <tr>
          <td></td>
          <td>)</td>
          <td></td><td></td>
        </tr>
      </table>
</div><div class="memdoc">

<p>push：generic_push_relabel算法的push操作。算法导论26章26.4节 </p>
<dl class="params"><dt>Parameters</dt><dd>
  <table class="params">
    <tr><td class="paramname">graph:指定流网络。它必须非空，否则抛出异常</td><td></td></tr>
    <tr><td class="paramname">u_id</td><td>结点u的id，必须有效否则抛出异常 </td></tr>
    <tr><td class="paramname">v_id</td><td>结点v的id，必须有效否则抛出异常 </td></tr>
    <tr><td class="paramname">flow</td><td>预流的引用（执行过程中会更新预流） </td></tr>
  </table>
  </dd>
</dl>
<dl class="section return"><dt>Returns</dt><dd>: void</dd></dl>
<p>如果u_id或者v_id无效，则抛出异常：</p>
<ul>
<li>如果指定的顶点<code>id</code>不在<code>[0,N)</code>之间，则无效</li>
<li>如果不存在某个顶点与指定的顶点<code>id</code>相同，则无效</li>
</ul>
<p>如果一个结点 u是一个溢出结点，则至少有一条入边，假设为(v,u)，且f(v,u)&gt;0。此时残留网络G_f中的边c_f(u,v)&gt;0。如果此时还有h(u)=h(v)+1， 则可以对边(u,v)执行push操作。</p>
<p>因为结点u有一个正的超额流u.e，且边(u,v)的残余容量为正，因此可以增加结点u到v的流，增加的幅度为min(u.e,c_f(u,v))，这种幅度的增加不会导致 u.e为负值或者容量 c(u,v) 被突破</p>
<p>push操作步骤：</p>
<ul>
<li>计算残余容量 c_f(u,v)</li>
<li>计算流的增加幅度 delt_f=min(u.e,c_f(u,v))</li>
<li>更新流：<ul>
<li>如果 (u,v) 属于 E，则 f(u,v) += delt_f</li>
<li>如果 (v,u) 属于 E，则 f(v,u) -= delt_f</li>
</ul>
</li>
<li>更新溢出流量：<ul>
<li>u.e -= delt(u,v)</li>
<li>v.e += delt(u,v)</li>
</ul>
</li>
</ul>
<blockquote class="doxtable">
<ul>
<li>由顶点的<code>key</code>属性存储超额流量e *</li>
<li>执行push(u,v)时，要求存在残留边 (u,v)属于Ef，且c_f(u,v)&gt;0；否则抛出异常</li>
<li>执行push(u,v)时，要求 u.e&gt;0；否则抛出异常</li>
</ul>
</blockquote>

<p>Definition at line <a class="el" href="genericpushrelabel_8h_source.html#l00067">67</a> of file <a class="el" href="genericpushrelabel_8h_source.html">genericpushrelabel.h</a>.</p>

</div>
</div>
<a class="anchor" id="a143924362cc9f23ca452c3ca0e292ff3"></a>
<div class="memitem">
<div class="memproto">
<div class="memtemplate">
template&lt;typename GraphType &gt; </div>
      <table class="memname">
        <tr>
          <td class="memname">void IntroductionToAlgorithm::GraphAlgorithm::relabel </td>
          <td>(</td>
          <td class="paramtype">std::shared_ptr&lt; GraphType &gt;&#160;</td>
          <td class="paramname"><em>graph</em>, </td>
        </tr>
        <tr>
          <td class="paramkey"></td>
          <td></td>
          <td class="paramtype">typename GraphType::VIDType&#160;</td>
          <td class="paramname"><em>u_id</em>, </td>
        </tr>
        <tr>
          <td class="paramkey"></td>
          <td></td>
          <td class="paramtype">const std::array&lt; std::array&lt; typename GraphType::EWeightType, GraphType::NUM &gt;, GraphType::NUM &gt; &amp;&#160;</td>
          <td class="paramname"><em>flow</em>&#160;</td>
        </tr>
        <tr>
          <td></td>
          <td>)</td>
          <td></td><td></td>
        </tr>
      </table>
</div><div class="memdoc">

<p>relabel：generic_push_relabel算法的relabel操作。算法导论26章26.4节 </p>
<dl class="params"><dt>Parameters</dt><dd>
  <table class="params">
    <tr><td class="paramname">graph:指定流网络。它必须非空，否则抛出异常</td><td></td></tr>
    <tr><td class="paramname">u_id</td><td>结点u的id，必须有效否则抛出异常 </td></tr>
    <tr><td class="paramname">flow</td><td>预流 </td></tr>
  </table>
  </dd>
</dl>
<dl class="section return"><dt>Returns</dt><dd>: void</dd></dl>
<p>如果结点u溢出（如果不是溢出则抛出异常），并且对于所有边(u,v)属于E_f(残留网络G_f中的边)，有u.h&lt;=v.h，则可以对结点u执行relabel操作。 当调用relabel操作时，E_f必须包含至少一条从结点u出发的边，否则抛出异常。</p>
<p>relabel 步骤：</p>
<ul>
<li>计算 min{v.h:(u,v)属于E_f}</li>
<li>u.h=1+ min{v.h:(u,v)属于E_f}</li>
</ul>
<p>当对于存在边(u,v)属于E_f(残留网络G_f中的边)，有u.h&gt;v.h时，抛出异常 </p>

<p>Definition at line <a class="el" href="genericpushrelabel_8h_source.html#l00184">184</a> of file <a class="el" href="genericpushrelabel_8h_source.html">genericpushrelabel.h</a>.</p>

</div>
</div>
<a class="anchor" id="abafb73bda29c4e389edb048a5e5d8d2b"></a>
<div class="memitem">
<div class="memproto">
<div class="memtemplate">
template&lt;typename GraphType &gt; </div>
      <table class="memname">
        <tr>
          <td class="memname">std::array&lt;std::array&lt;typename GraphType::EWeightType,GraphType::NUM&gt;,GraphType::NUM&gt; IntroductionToAlgorithm::GraphAlgorithm::relabel_to_front </td>
          <td>(</td>
          <td class="paramtype">std::shared_ptr&lt; GraphType &gt;&#160;</td>
          <td class="paramname"><em>graph</em>, </td>
        </tr>
        <tr>
          <td class="paramkey"></td>
          <td></td>
          <td class="paramtype">typename GraphType::VIDType&#160;</td>
          <td class="paramname"><em>src</em>, </td>
        </tr>
        <tr>
          <td class="paramkey"></td>
          <td></td>
          <td class="paramtype">typename GraphType::VIDType&#160;</td>
          <td class="paramname"><em>dst</em>&#160;</td>
        </tr>
        <tr>
          <td></td>
          <td>)</td>
          <td></td><td></td>
        </tr>
      </table>
</div><div class="memdoc">

<p>relabel_to_front：最大流的前置重贴标签算法。算法导论26章26.5节 </p>
<dl class="params"><dt>Parameters</dt><dd>
  <table class="params">
    <tr><td class="paramname">graph:指定流网络。它必须非空，否则抛出异常</td><td></td></tr>
    <tr><td class="paramname">src</td><td>流的源点，必须有效否则抛出异常 </td></tr>
    <tr><td class="paramname">dst</td><td>流的汇点，必须有效否则抛出异常 </td></tr>
  </table>
  </dd>
</dl>
<dl class="section return"><dt>Returns</dt><dd>: 最大流矩阵</dd></dl>
<p>如果src、dst任何一个顶点无效，则抛出异常：</p>
<ul>
<li>如果指定的顶点<code>id</code>不在<code>[0,N)</code>之间，则无效</li>
<li>如果不存在某个顶点与指定的顶点<code>id</code>相同，则无效</li>
</ul>
<h2>最大流</h2>
<p>流网络G=（V,E）是一个有向图，图中每条边(u,v)属于E都有一个正的容量值c(u,v)&gt;0。而且如果边集合E中包含一条边(u,v)，则图中不存在反向边 (v,u)。为方便起见，假设(u,v)不属于E,定义c(u,v)=0（即无效权重为0），并且在图中不允许自循环。</p>
<p>在流网络中存在两个特殊点：源结点s和汇点t。假定每一个结点都在从源点s到汇点t的某条路径上。即对于每个结点v属于E，存在某条路径 s&ndash;&gt;v&ndash;&gt;t。</p>
<p>G中的流是一个实值函数f:V*V&ndash;&gt;R，满足下面两条性质：</p>
<ul>
<li>容量限制：对于所有结点u,v属于V，要求0&lt;= f(u,v) &lt;= c(u,v)</li>
<li>流量守恒： 对于所有结点u属于V-{s,t}，要求：从u进入的流等于从u出去的流</li>
</ul>
<p>对于(u,v)不属于E的情况，从结点u到v之间没有流，因此f(u,v)=0。我们称非负数值f(u,v)为从结点u到v的流。一个流f的值 |f|=从源点流出的总流量- 流入源结点的总流量</p>
<p>最大流问题：给定流网络G、一个源结点s、一个汇点t,找出值最大的一个流</p>
<h2>relabel_to_front 算法</h2>
<h3>算法原理</h3>
<p>&gt;本节的一些概念参考 generic_push_relabel 算法</p>
<p>推送-重贴标签方法允许我们以任意次序执行基本操作。但是，如果仔细选择这个次序，并且对网络数据结构进行高效管理，我们可以获取更高的算法性能。</p>
<p>前置重贴标签算法在执行过程中维持一个网络中的结点的链表。算法从头到尾对链表进行扫描，每次选择一个溢出结点u。 然后对结点u进行“释放”，即对所选结点执行推送操作和重贴标签操作，直到结点u不再拥有正值的超额流量为止。 每次在算法对一个结点进行重贴标签操作时，我们都将该结点移动到链表的最前面（也就是“前置重贴标签算法”的名字由来），然后算法进行一次新的扫描。</p>
<p>设图G=(V,E)是一个源点s汇点t的流网络，f是G中的一个预流（它满足容量限制单不满足流量守恒性质），h是一个高度函数。 对于边(u,v)，如果c_f(u,v)&gt;0且h(u)=h(v)+1，则边(u,v)是一条许可边；否则边(u,v)是一条非许可边。许可边意义是：在残余网络中， 流可以经过它进行推送的边。许可网络指图G_f_h=(V,E_f_h)，其中E_f_h是许可边的集合。</p>
<p>在前置重贴标签算法中，我们将所有边都组织为“邻接链表”。给定流网络G=(V,E)，对于结点u属于V，其邻接链表u.N是结点u在图G 中的邻接结点所构成的一个单链表（包括了u的上游和下游的邻接结点）：若边(u,v)属于E或者边(v,u)属于E，则结点v将出现在链表u.N中。 &gt;邻接链表u.N包含的结点是所有可能存在残留边(u,v)的结点v</p>
<p>属性u.N.head指向的是邻接表u.N中的第一个结点；v.next-neighbor指向的是邻接链表u.N中位于结点v后面的一个结点。如果v是链表中最后一个结点， 则该指针的值为NIL</p>
<p>前置重贴标签算法以任意次序遍历每一个邻接链表，该次序在算法整个执行过程中不变。对于每个结点u，属性u.current指向的是u.N 链表中当前正在考虑的结点。初始情况下u.current指向u.N.head</p>
<h3>基本操作</h3>
<h4>discharge 操作</h4>
<p>对于溢出结点u,如果将其所有多余的流通过许可边推送到相邻的结点上，则称该结点得到释放。 在释放过程中，需要对结点u进行重贴标签操作，这使得从结点u发出的边成为许可边。discharge(u) 操作步骤如下：</p>
<ul>
<li>循环，条件为u.e&gt;0，循环内操作为：<ul>
<li>获取u.current，假设为v</li>
<li>如果v为空，即遍历到u.N链表的末尾，则对u执行relabel操作，然后将u.current指向u.N链表的头部</li>
<li>如果 v非空，且满足 push 操作的条件(c_f(u,v)&gt;0且 u.h=v.h+1)，则执行push操作</li>
<li>如果 v 非空，但不满足 push 操作，则 u.current指向u.N链表的下一个结点</li>
</ul>
</li>
</ul>
<h3>算法步骤</h3>
<ul>
<li>初始化预流操作（与 generic_push_relabel 算法相同）</li>
<li>对所有的非s、t的结点，将它们加入到链表L中（顺序任意）</li>
<li>对所有的非s、t的结点u,初始化u.current为u.N.head</li>
<li>设置u为L.head</li>
<li>循环，条件为u!=NIL，循环中操作：<ul>
<li>保留u.h为oldh</li>
<li>对u执行discharge操作</li>
<li>如果u.h&gt;oldh，证明对u执行了重贴标签操作，此时将u移动到L的头部</li>
<li>u=u.next（提取u在L中的下一个）</li>
</ul>
</li>
</ul>
<h3>算法性能</h3>
<p>算法性能：时间复杂度 O(V^3) </p>

<p>Definition at line <a class="el" href="relabeltofront_8h_source.html#l00280">280</a> of file <a class="el" href="relabeltofront_8h_source.html">relabeltofront.h</a>.</p>

</div>
</div>
<a class="anchor" id="afe2bd83fca7df7e07ece9a59b8e7f5a6"></a>
<div class="memitem">
<div class="memproto">
<div class="memtemplate">
template&lt;typename VertexType &gt; </div>
      <table class="memname">
        <tr>
          <td class="memname">void IntroductionToAlgorithm::GraphAlgorithm::relax </td>
          <td>(</td>
          <td class="paramtype">std::shared_ptr&lt; VertexType &gt;&#160;</td>
          <td class="paramname"><em>from</em>, </td>
        </tr>
        <tr>
          <td class="paramkey"></td>
          <td></td>
          <td class="paramtype">std::shared_ptr&lt; VertexType &gt;&#160;</td>
          <td class="paramname"><em>to</em>, </td>
        </tr>
        <tr>
          <td class="paramkey"></td>
          <td></td>
          <td class="paramtype">typename VertexType::KeyType&#160;</td>
          <td class="paramname"><em>weight</em>&#160;</td>
        </tr>
        <tr>
          <td></td>
          <td>)</td>
          <td></td><td></td>
        </tr>
      </table>
</div><div class="memdoc">

<p>relax：单源最短路径的松弛操作，算法导论24章24.1节 </p>
<dl class="params"><dt>Parameters</dt><dd>
  <table class="params">
    <tr><td class="paramname">from:松弛有向边的起始结点，必须非空。若为空则抛出异常</td><td></td></tr>
    <tr><td class="paramname">to：松弛有向边的终止结点，必须非空且不等于from。若为空或者等于from则抛出异常</td><td></td></tr>
    <tr><td class="paramname">weight:有向边的权重</td><td></td></tr>
  </table>
  </dd>
</dl>
<dl class="section return"><dt>Returns</dt><dd>: void</dd></dl>
<p>对每一个结点v来说，我们维持一个属性v.key，它记录了从源结点s到结点v的最短路径权重的上界。我们称v.key为s到v的最短路径估计。</p>
<p>松弛过程是测试一下是否可以对从s到v的最短路径进行改善的过程，测试方法为： 将结点s到u之间的最短路径估计加上(u,v)边的权重，并与当前的s到v之间的最短路径估计进行比较。如果前者较小则对v.key和v.parent进行更新。</p>
<p>性能：时间复杂度O(1) </p>

<p>Definition at line <a class="el" href="bellmanford_8h_source.html#l00082">82</a> of file <a class="el" href="bellmanford_8h_source.html">bellmanford.h</a>.</p>

</div>
</div>
<a class="anchor" id="ac368f242de9f06c7d936cba4aa0ab40b"></a>
<div class="memitem">
<div class="memproto">
<div class="memtemplate">
template&lt;typename GraphType &gt; </div>
      <table class="memname">
        <tr>
          <td class="memname">bool IntroductionToAlgorithm::GraphAlgorithm::same_component </td>
          <td>(</td>
          <td class="paramtype">std::shared_ptr&lt; GraphType &gt;&#160;</td>
          <td class="paramname"><em>graph</em>, </td>
        </tr>
        <tr>
          <td class="paramkey"></td>
          <td></td>
          <td class="paramtype">typename GraphType::VIDType&#160;</td>
          <td class="paramname"><em>id1</em>, </td>
        </tr>
        <tr>
          <td class="paramkey"></td>
          <td></td>
          <td class="paramtype">typename GraphType::VIDType&#160;</td>
          <td class="paramname"><em>id2</em>&#160;</td>
        </tr>
        <tr>
          <td></td>
          <td>)</td>
          <td></td><td></td>
        </tr>
      </table>
</div><div class="memdoc">

<p>same_component：返回无向图的两个顶点是否位于同一个连通分量中。算法导论21章21.1节 </p>
<dl class="params"><dt>Parameters</dt><dd>
  <table class="params">
    <tr><td class="paramname">graph:指向图的强指针，必须非空。若为空则抛出异常</td><td></td></tr>
    <tr><td class="paramname">id1:第一个顶点，必须有效。若无效则抛出异常</td><td></td></tr>
    <tr><td class="paramname">id2:第二个顶点，必须有效。若无效则抛出异常</td><td>当满足以下条件之一时，id无效的情况：</td></tr>
  </table>
  </dd>
</dl>
<ul>
<li>id小于0或者大于等于<code>GraphType::NUM</code></li>
<li><code>graph-&gt;vertexes.at(id1)</code>为空</li>
</ul>
<p>在执行 same_component函数之前必须先执行 connected_component函数对无向图进行预处理。 </p>

<p>Definition at line <a class="el" href="connectedcomponent_8h_source.html#l00093">93</a> of file <a class="el" href="connectedcomponent_8h_source.html">connectedcomponent.h</a>.</p>

</div>
</div>
<a class="anchor" id="a6d058c2aaa8714778b3f2ab8a24ff232"></a>
<div class="memitem">
<div class="memproto">
<div class="memtemplate">
template&lt;typename GraphType &gt; </div>
      <table class="memname">
        <tr>
          <td class="memname">const std::vector&lt;std::vector&lt;typename GraphType::VIDType&gt; &gt; IntroductionToAlgorithm::GraphAlgorithm::scc </td>
          <td>(</td>
          <td class="paramtype">std::shared_ptr&lt; GraphType &gt;&#160;</td>
          <td class="paramname"><em>graph</em></td><td>)</td>
          <td></td>
        </tr>
      </table>
</div><div class="memdoc">

<p>scc：强连通分量，算法导论22章22.5节 </p>
<dl class="params"><dt>Parameters</dt><dd>
  <table class="params">
    <tr><td class="paramname">graph:指向图的强引用，必须非空。若为空则抛出异常</td><td></td></tr>
  </table>
  </dd>
</dl>
<dl class="section return"><dt>Returns</dt><dd>:强连通分量的<code>std::vector</code>，每一个强连通分量，由一组顶点<code>id</code>组成的<code>std::vector</code>表示。</dd></dl>
<p>有向图G=(V,E)的强连通分量是一个最大结点集合C，C是V的子集。对于C中的任意一对结点u,v来说，路径u&ndash;&gt;v和路径v&ndash;&gt;u同时存在。即结点u和结点v之间相互可以到达。</p>
<p>在强连通分量的算法中，需要用到图G的转置G_T。定义G_T=(V,E_T),其中E_T={(u,v):(v,u)属于E}，即G_T中的边是G中的边进行反向获得。</p>
<ul>
<li>图G和图G_T的强连通分量相同</li>
<li>可以证明，<code>scc</code>算法得到的就是强连通分量。证明见《算法导论》</li>
</ul>
<p>强连通分量算法步骤：</p>
<ul>
<li>对原图G执行深度优先搜索，并获取每个结点的完成时间 finish_time</li>
<li>对转置图G_T执行深度优先搜索，但是按照 G中结点的一个排序来搜索（这个排序是按照finish_time的降序）</li>
<li>G_T的深度优先森林就是强连通分量</li>
</ul>
<p>性能：时间复杂度O(V+E) </p>

<p>Definition at line <a class="el" href="strongconnectedcomponent_8h_source.html#l00048">48</a> of file <a class="el" href="strongconnectedcomponent_8h_source.html">strongconnectedcomponent.h</a>.</p>

</div>
</div>
<a class="anchor" id="a804241e72be5f4c031190bc12a6b73a2"></a>
<div class="memitem">
<div class="memproto">
<div class="memtemplate">
template&lt;typename GraphType &gt; </div>
      <table class="memname">
        <tr>
          <td class="memname">std::vector&lt;typename GraphType::VIDType&gt; IntroductionToAlgorithm::GraphAlgorithm::topology_sort </td>
          <td>(</td>
          <td class="paramtype">std::shared_ptr&lt; GraphType &gt;&#160;</td>
          <td class="paramname"><em>graph</em></td><td>)</td>
          <td></td>
        </tr>
      </table>
</div><div class="memdoc">

<p>topology_sort：拓扑排序，算法导论22章22.4节 </p>
<dl class="params"><dt>Parameters</dt><dd>
  <table class="params">
    <tr><td class="paramname">graph:指向图的强引用，必须非空。若为空则抛出异常</td><td></td></tr>
  </table>
  </dd>
</dl>
<dl class="section return"><dt>Returns</dt><dd>:拓扑排序结果，它是顶点<code>id</code>组成的<code>std::vector</code>，表示顶点的拓扑排序后的顺序</dd></dl>
<p>对于一个有向无环图G=（V，E)，其拓扑排序是G中所有结点的一种线性次序，该次序满足如下条件： 如果图G包含边(u,v)，则结点u在拓扑排序中处于结点v的前面。</p>
<p>拓扑排序原理：对有向无环图G进行深度优先搜索。每当完成一个结点时，将该结点插入到拓扑排序结果的头部。 因此如果将结点按照完成时间降序排列，则得到的就是拓扑排序的结果。</p>
<p>引理：一个有向图G=(V,E)是无环的当且仅当对其进行深度优先搜索时不产生后向边。</p>
<p>性能：时间复杂度O(V+E) </p>

<p>Definition at line <a class="el" href="topologysort_8h_source.html#l00045">45</a> of file <a class="el" href="topologysort_8h_source.html">topologysort.h</a>.</p>

</div>
</div>
<a class="anchor" id="a19237111c3b1ec2717c5e1aefe2f6d9b"></a>
<div class="memitem">
<div class="memproto">
<div class="memtemplate">
template&lt;typename T &gt; </div>
      <table class="memname">
        <tr>
          <td class="memname">T IntroductionToAlgorithm::GraphAlgorithm::unlimit </td>
          <td>(</td>
          <td class="paramname"></td><td>)</td>
          <td></td>
        </tr>
      </table>
</div><div class="memdoc">

<p>unlimit：返回正无穷的函数 </p>
<dl class="section return"><dt>Returns</dt><dd>: 正无穷大的数</dd></dl>
<p>将本函数的返回值定义为正无穷。在算法导论图算法中，经常用到正无穷。通常对正无穷的操作是:</p>
<ul>
<li>将边的权重或者节点的<code>key</code>设为正无穷</li>
<li>对正无穷加、减一个有限的数，结果还是正无穷</li>
</ul>
<p>这里将<code>std::numeric_limits&lt;T&gt;::max()/2</code>设为正无穷，考虑到正无穷加上一个较大的数必须保证不能溢出 </p>

<p>Definition at line <a class="el" href="header_8h_source.html#l00111">111</a> of file <a class="el" href="header_8h_source.html">header.h</a>.</p>

</div>
</div>
<a class="anchor" id="a5fbba98b1c6a8b55f026158acc815768"></a>
<div class="memitem">
<div class="memproto">
<div class="memtemplate">
template&lt;typename GraphType &gt; </div>
      <table class="memname">
        <tr>
          <td class="memname">void IntroductionToAlgorithm::GraphAlgorithm::visit </td>
          <td>(</td>
          <td class="paramtype">std::shared_ptr&lt; GraphType &gt;&#160;</td>
          <td class="paramname"><em>graph</em>, </td>
        </tr>
        <tr>
          <td class="paramkey"></td>
          <td></td>
          <td class="paramtype">typename GraphType::VIDType&#160;</td>
          <td class="paramname"><em>v_id</em>, </td>
        </tr>
        <tr>
          <td class="paramkey"></td>
          <td></td>
          <td class="paramtype">int &amp;&#160;</td>
          <td class="paramname"><em>time</em>, </td>
        </tr>
        <tr>
          <td class="paramkey"></td>
          <td></td>
          <td class="paramtype">std::function&lt; void(typename GraphType::VIDType, int)&gt;&#160;</td>
          <td class="paramname"><em>pre_action</em> = <code>[](typename&#160;GraphType::VIDType,int){}</code>, </td>
        </tr>
        <tr>
          <td class="paramkey"></td>
          <td></td>
          <td class="paramtype">std::function&lt; void(typename GraphType::VIDType, int)&gt;&#160;</td>
          <td class="paramname"><em>post_action</em> = <code>[](typename&#160;GraphType::VIDType,int){}</code>&#160;</td>
        </tr>
        <tr>
          <td></td>
          <td>)</td>
          <td></td><td></td>
        </tr>
      </table>
</div><div class="memdoc">

<p>visit：深度优先搜索的辅助函数，用于访问顶点，算法导论22章22.3节 </p>
<dl class="params"><dt>Parameters</dt><dd>
  <table class="params">
    <tr><td class="paramname">graph:指向图的强引用，必须非空。若为空则抛出异常</td><td></td></tr>
    <tr><td class="paramname">v_id:待访问顶点的&lt;tt&gt;id&lt;/tt&gt;，必须有效。如果无效则抛出异常</td><td></td></tr>
    <tr><td class="paramname">time:访问时刻，是一个引用参数，确保每次&lt;tt&gt;visit&lt;/tt&gt;都访问同一个时钟。</td><td></td></tr>
    <tr><td class="paramname">pre_action:一个可调用对象，在每次发现一个顶点时调用，调用参数为该顶点的&lt;tt&gt;id&lt;/tt&gt;以及发现时间&lt;tt&gt;time&lt;/tt&gt;。默认为空操作，即不进行任何操作</td><td></td></tr>
    <tr><td class="paramname">post_action:一个可调用对象，在每次对一个顶点搜索完成时调用，调用参数为该顶点的&lt;tt&gt;id&lt;/tt&gt;以及完成时间&lt;tt&gt;time&lt;/tt&gt;。默认为空操作，即不进行任何操作</td><td><code>v_id</code>在以下情况下无效：</td></tr>
  </table>
  </dd>
</dl>
<ul>
<li><code>v_id</code>不在区间<code>[0,N)</code>之间时，<code>v_id</code>无效</li>
<li><code>graph</code>中不存在某个顶点的<code>id</code>等于<code>v_id</code>时，<code>v_id</code>无效</li>
</ul>
<p>在每次对一个结点调用visit的过程中，结点v_id的初始颜色都是白色。然后执行下列步骤：</p>
<ul>
<li>将全局时间 time 递增</li>
<li>发现结点 v_id</li>
<li>对结点 v_id 的每一个相邻结点进行检查，在相邻结点是白色的情况下递归访问该相邻结点</li>
<li>当结点 v_id 的相邻结点访问完毕，则全局时间 time 递增，然后将结点 v_id 设置为完成状态 </li>
</ul>

<p>Definition at line <a class="el" href="dfs_8h_source.html#l00049">49</a> of file <a class="el" href="dfs_8h_source.html">dfs.h</a>.</p>

</div>
</div>
</div><!-- contents -->
</div><!-- doc-content -->
<!-- start footer part -->
<div id="nav-path" class="navpath"><!-- id is needed for treeview function! -->
  <ul>
    <li class="navelem"><a class="el" href="namespace_introduction_to_algorithm.html">IntroductionToAlgorithm</a></li><li class="navelem"><a class="el" href="namespace_introduction_to_algorithm_1_1_graph_algorithm.html">GraphAlgorithm</a></li>
    <li class="footer">Generated by
    <a href="http://www.doxygen.org/index.html">
    <img class="footer" src="doxygen.png" alt="doxygen"/></a> 1.8.10 </li>
  </ul>
</div>
</body>
</html>
